Tag Archives: 組合數學

二項式係數與組合問題

本文的閱讀等級:初級 在組合數學,從包含 個元素的集合中選取 個元素的組合數 (不考慮次序),記為 ,稱為二項式係數 (binomial coefficient)。我們先推導 的計算公式。設想有 個人在排隊買電影票,我們可以從 個人中選一人排在第一個位置,再從剩下的 個人裡選一人排在第二個位置,餘此類推,共有 種排列方式。再考慮第二種算法。電影院為鼓勵大眾及早排隊購票,特意準備了 張椅子,,供給排在最前面的 個人歇坐。針對這個情況,從 個人中選取 個人進入歇坐區有 種方式,歇坐區內的 個人有 種排列方式,歇坐區外的 個人有 種排列方式,因此 個人排隊共有 種排列方式。合併上面兩個結果,即得 , 並定義邊界條件 。根據對稱性,。   問題1:你邀請 位好友參加生日宴會,至少有一人出席生日宴會的來賓組合共有多少種? 因為至少有一個人出席派對,出席來賓的組合方式有 。   問題2:投擲一枚公正硬幣 次,出現至少一次正面的機率 (概率) 是多少? 出現 次反面的機率是 ,所以出現至少一次正面的機率是 … Continue reading

Posted in 機率統計 | Tagged , , , | Leave a comment

費雪不等式

本文的閱讀等級:中級 英國統計學家、演化生物學家與遺傳學家費雪 (Ronald Fisher) 是現代統計學的創建者之一。今天我們使用的許多統計方法,例如,變異數分析 (方差分析,簡稱ANOVA)、最大似然估計與費雪線性判別等,都是他的發明貢獻。本文要探討的主題是在實驗設計時碰到的一個組合數學問題。考慮包含 個元素的集合 。令 為 的 個相異非空子集合。令 代表一集合 的基數 (cardinal number),即所包含的元素個數。 費雪不等式:若所有的 滿足 ,則 。 費雪的原始論文以組合數學解釋[1],本文討論多種線性代數證法,使用的基本工具包括矩陣秩、行列式、特徵值、線性獨立與正定 (類似應用見“有限體與模算術”)。

Posted in 線性代數專欄, 應用之道 | Tagged , , , , , , | Leave a comment

第二類 Stirling 數與貝爾數

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

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

有向無環圖與 (0,1) 矩陣的特徵值

本文的閱讀等級:中級 若一個矩陣 的每一元 為 或 ,我們稱之為 (0,1) 矩陣。2003年任職 Wolfram 研究中心的韋斯坦 (Eric W. Weisstein) 在計算 階 (0,1) 矩陣,,的特徵值時,發現所有特徵值皆為正實數[1]的 (0,1) 矩陣總數為下列序列: 在圖論中,若一個有向圖無法從某個頂點出發經過若干條邊回到該點,則稱之為有向無環圖 (directed acyclic graph,簡稱DAG)。韋斯坦得到的序列恰巧與包含 個標記頂點的有向無環圖數的前五項相等[2]: 自然地,韋斯坦猜想這兩個數列完全相同。圖一顯示 的所有標記有向無環圖。2004年麥凱 (Brendan D. McKay) 等人證明了韋斯坦猜想:包含 個標記頂點的有向無環圖與特徵值皆為正實數的 階 矩陣存在一對一的關係[3]。底下介紹一個精巧的證明。

Posted in 線性代數專欄, 圖論, 應用之道 | Tagged , , , , , , , , | 7 Comments

遞迴關係式的母函數解法

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

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

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

本文的閱讀等級:初級 本文是探討電影《心靈捕手》中數學問題的完結篇。這回麻省理工學院朗博教授和威爾將聯手出擊,他們的目標要破解一道組合數學問題:求3─太陽圖 (3-sun graph) 的色多項式 (chromatic polynomial),其中 的頂點集合是 ,邊集合是 (見圖一)。

Posted in 圖論 | Tagged , , , | Leave a comment

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

本文的閱讀等級:中級 朗博教授公告在走廊黑板的第二個挑戰問題抄錄於下: (1) How many trees are there with labeled vertices? (2) Draw all the homeomorphically irreducible trees with . 威爾的答案:(1) ,(2) 8 棵樹 (見電影劇照)。這兩個問題屬於組合數學的範疇。廣義的組合數學就是離散數學,狹義的組合數學是圖論、代數結構、數理邏輯等的總稱[1]。為了讀懂朗博教授的問題,我們先要瞭解一些關於樹 (圖論的一個主題) 的基本知識。

Posted in 圖論 | Tagged , , , , , , | Leave a comment

二項式係數公式

本文的閱讀等級:初級 令 表示 個元素構成的集合。從 中選取 個元素的可能方式稱為組合,譬如,從 選取 個元素的組合如下: 。 計算 的 —組合數並不困難:想像 個元素排成一列,選取領先的 個元素,共有 種可能。這 個元素可以任意置換,每一種 —組合重複出現 次。所以,從包含 個元素的集合 中選取 個元素的組合數,記為 ,計算如下: 。 譬如,。我們稱 為二項式係數 (binomial coefficient)。這個名稱的由來係因 , 其中 是 的係數。從二項式係數的表達式可知縱使 不是整數,我們依然能定義 。為便於識別,我們用 代表任一實數, 代表任一整數,定義 。 見下表,非零的部分稱為帕斯卡三角形 (見“特殊矩陣 (15):Pascal 矩陣 … Continue reading

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

有限體與模算術

本文的閱讀等級:中級 從前,在一個遙遠的小城裡住著 個居民,他們主要的職業是組成各式各樣的俱樂部。由於某種不明的原因,不斷擴增的俱樂部開始威脅小城的生存。為了管制俱樂部總量,市議會決議通過兩條看似天真的法令: 每一個俱樂部必須有奇數個會員。 任兩個俱樂部必須有偶數個相同的會員。 小城市長宣稱:「有了這兩條法令,本城的俱樂部總數不會多於居民人口。」下面我們用線性代數方法來證明這個組合數學定理[1]。

Posted in 線性代數專欄, 向量空間 | Tagged , , , , , , , | Leave a comment

特殊矩陣 (15):Pascal 矩陣 (下)

本文的閱讀等級:中級 我們將前文“特殊矩陣 (15):Pascal 矩陣 (上)”的主要結果整理於下。首先定義一 階創造矩陣 :若 ,,否則 。創造矩陣 衍生出矩陣指數,如下: , 其中 是實數。因為 是冪零矩陣,即對於 ,,故 可表示為 的 次多項式: 。 代入 ,可得 ;代入 ,可得 。展開上式等號右邊即推得 的 元:若 , ,否則 。提醒讀者,我們定義 若 , 若 。令帕斯卡矩陣為 (亦即若 ,,否則 ),所以對於任意實數 ,,並有以下必然結果: 。 當 ,即得 … Continue reading

Posted in 特殊矩陣, 線性代數專欄 | Tagged , , , , , , , | 3 Comments