Tag Archives: 母函數

第二類 Stirling 數與貝爾數

Posted on 10/28/2013 by ccjou

本文的閱讀等級：中級 考慮這個組合數學問題：包含 個元素的集合 劃分為 個等價類的方法數是多少？也就是說，總共有多少種方式將集合 劃分為 個兩兩不交集的非空子集？以符號 或 代表此數，稱之為第二類 Stirling 數 (因蘇格蘭數學家 James Stirling 而得名[1])。明顯地， 。看一個 的例子， 劃分為 類的所有可能方式如下： 因此， 。考慮集合 加入數字 ，區分為兩個情況：數字 單獨構成一類，只有 一種劃分法；數字 加入上面的 種劃分的其中一個等價類，共有 種可能。所以， 。重複此程序可以歸納出 。不過，這個演繹過程不容易推廣至 。下面我們運用母函數 (生成函數，generating function) 方法推導第二類 Stirling 數的顯式表達式。

Posted in 特別主題 | Tagged , , , , | 3 Comments

遞迴關係式的母函數解法

Posted on 10/23/2013 by ccjou

本文的閱讀等級：初級 美國數學教授維爾夫 (Herbert Wilf) 說[1]：「母函數 (生成函數，generating function) 是一列用來展示一串數字的掛衣架。」母函數是一數列 的一種形式冪級數 (formal power series)，其中每一項的係數可以提供關於這個數列的訊息。母函數有多種不同的形式，數列 的普通母函數為 母函數 本身並不是一個從某個定義域映射至某個值域的函數，變數 沒有甚麼特別的意義，取名「函數」僅是出於歷史原因。母函數是一個代數物件而非分析物件，我們只對它的表達形式感興趣，並不關心它是否收斂。母函數經常源自遞迴關係式 (即差分方程)。本文將介紹如何利用母函數方法解出遞迴關係式的代數式。由於我們完全忽略收斂性，母函數方法是否能經得起推敲不免令人生疑。不過母函數至少能夠導出遞迴關係式的猜想，而猜想又可以用數學歸納法來證明。

Posted in 特別主題 | Tagged , , , , , , | Leave a comment

電影《心靈捕手》的數學問題 (一)

Posted on 09/30/2013 by ccjou

本文的閱讀等級：中級 美國馬里蘭大學馬尼爾‧蘇里 (Manil Suri) 教授說[1]： 在新聞媒體或文化領域，很少會出現數學這個主題。很多時候，當數學出現在一部小說或電影中時，我就會想起契訶夫諺語中的槍：如果一個數學家不發瘋，就別讓他出場。對數學的焦慮感，像厚厚的陰霾一樣籠罩着萬事萬物。   我知道關於「數學與人物」的電影法則包括 如果你是一個正常人，那麼你應當害怕或討厭數學。 如果你解開別人解不出的數學問題，那麼你不是書呆子就是精神異常者。 如果你的數學本來其爛無比，有一天卻突然擁有超強的特異能力，那麼你可能被外星人附體或腦部受到不明來源的輻射汙染。   在電影《心靈捕手》(Good Will Hunting)，麻省理工學院的朗博教授 (Gerald Lambeau) 為激勵學生上進，他在走廊黑板公布數學難題並保證答對者將可名利雙收。清潔工威爾 (Will Hunting) 擁有過人的天賦，性格叛逆亟需心理治療，但尚未惡化到發瘋的地步[2]。朗博教授和威爾同在一棟大樓工作，不過兩人沒有任何交集。本文討論朗博教授張貼的第一個問題。下面是電影片段 (字幕見[3])。

Posted in 圖論 | Tagged , , , , , , | 5 Comments