Tag Archives: 組合數學

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

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

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

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