Tag Archives: 母函數

第二類 Stirling 數與貝爾數

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

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

遞迴關係式的母函數解法

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

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

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

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

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