組合數學

廣義的組合數學（英語：Combinatorics）相當於離散數學，狹義的組合數學是組合計數、圖論、代數結構、數理邏輯等的總稱。但這只是不同學者在叫法上的區別。總之，組合數學是一門研究可數或離散對象的科學。隨着計算機科學日益發展，組合數學的重要性也日漸凸顯，因為計算機科學的核心內容是使用算法處理離散數據。

狹義的組合數學主要研究滿足一定條件的組態（也稱組合模型）的存在、計數以及構造等方面的問題。組合數學的主要內容有組合計數、組合設計(Combinatorial design)、組合矩陣(Combinatorial matrix theory)、組合最佳化（最佳組合）等。

歷史

An example of change ringing (with six bells), one of the earliest nontrivial results in graph theory.

最基本的組合數學的思想和枚舉的方法在古老時代就已經出現。西元前6世紀的古印度外科醫生妙聞指出可以由6種相異味道組合出63種相異結果（每種味道都可以選擇或不選擇，但不能都不選擇，因此有2⁶−1=63種組合）；古羅馬時期，希臘史學家普魯塔克與克律西波斯、喜帕恰斯討論了後來顯示與Schröder–Hipparchus數有關的枚舉問題；西元前3世紀的阿基米德在其數學文章Ostomachion中講述拼接拼圖的智力遊戲（tiling puzzle）。

中世紀時，組合數學持續發展（主要是歐洲外的文明）。西元850年的印度數學家Mahāvīra提供了關於排列數與組合的公式，甚至可能早在6世紀的印度數學家就對這些公式熟悉 。西元1140年哲學家與天文學家阿伯拉罕·伊本·埃茲拉確認了二項式系數的對稱性，而二項式系數公式則是由猶太人數學家吉爾松尼德在西元1321年得到。楊輝三角形最早可追溯至10世紀的數學論文，在中國則首現於13世紀南宋楊輝《詳解九章算法》。在英格蘭則出現與哈密頓迴路相關的例子。

文藝復興時期，與其他數學或科學領域一樣，組合數學再現生機。帕斯卡、牛頓、雅各布·白努利、歐拉等人的研究為此新興領域打下基礎。在更近代，西爾維斯特和馬克斯·馬奧尼也在組合計數和代數組合學有貢獻。數學家也對四色問題等圖論有極大興趣。

在20世紀下半葉，組合數學成長相當迅速，甚至出現數十種新的期刊和會議，這種成長某程度上是由與其他領域的連結與應用所帶動，如代數、概率論、泛函分析和數論。

組合數學中的著名問題

• 計算一些物品在特定條件下分組的方法數目。這些是關於排列、組合和整數分拆。
• 地圖着色問題：為地圖填色，每區用一色。如果要鄰區顏色相異，是否只需四色？這是圖論題。
• 船夫過河問題：船夫要把一匹狼、一隻羊和一棵菜運過河。只要船夫不在場，羊就會吃白菜、狼就會吃羊，但船每次只能運送一種東西。怎樣把所有東西運過河？這是線性規劃題。
• 中國郵差問題：由中華民國組合數學家管梅谷教授提出。郵差要穿過城市的每一條路至少一次，怎樣行走走過的路程最短？這不是NP完全問題，存在多項式複雜度算法：先求出度為奇數的點，用匹配算法算出這些點間的連接方式，然後再用歐拉路徑算法求解。也是圖論題。
• 任務分配問題（也稱分配問題）：有一些員工要完成一些任務。各員工完成不同任務用的時間都不同。每個員工只分配一項任務。每項任務只分給一個員工。怎樣分配員工與任務以使所花費的時間最少？也是線性規劃題。
• 如何構造幻方： 幻方為一方陣，填入不重複之自然數，並使其中每一縱列、橫列、對角線內數字之和皆相同。
• 數獨：遊戲一般由9個3×3個的九宮格組成。每一列的數字均須包含 1～9，不能缺少，也不能重複。每一宮(粗黑線圍起來的區域，通常是 3x3 的九宮格)的數字均須包含 1～9，不能缺少，也不能重複。^{參見Mathematics_of_Sudoku}

排列

主條目：排列

從$n$個元素取出$k$個元素，$k$個元素的排列數量為：

$P_{k}^{n}={\frac {n!}{(n-k)!}}$

以賽馬為例，有8匹馬參賽，玩家需在彩票上填入前三匹勝出的馬匹號碼，從8匹馬取出3匹來排前3名，排列數量為：

$P_{3}^{8}={\frac {8!}{(8-3)!}}=8\times 7\times 6=336$

因為有336種排列，因此玩家在一次填入中中獎的概率是：

$P={\frac {1}{336}}=0.00298$ (假設每匹馬贏的機會相等)

不過，中國大陸的教科書則是把從n取k的情況記作$P_{n}^{k}$或$A_{n}^{k}$（A代表Arrangement，即排列）。

上例是在取出元素不重複出現的狀況建立。

從$n$個元素取出$k$個元素，$k$個元素可以重複出現，這排列數量為：

$U_{k}^{n}=n^{k}$

以四星彩為例，10個數取4個，因可能重複所以排列數量為：

$U_{4}^{10}=10^{4}=10000$

這時的一次性添入中獎的概率就是：

$P={\frac {1}{10000}}=0.0001$

組合

主條目：組合

和排列不同的是，組合不考慮取出元素的順序。

從$n$個元素取出$k$個，$k$個元素的組合數量為：

$C_{k}^{n}={n \choose k}={\frac {P_{k}^{n}}{k!}}={\frac {n!}{k!(n-k)!}}$

中國大陸的教科書則是把從$n$取$k$的情況記作$C_{n}^{k}$。

以香港六合彩為例，六合彩49顆球選6顆的組合數量為：

$C_{6}^{49}={49 \choose 6}={\frac {49!}{6!43!}}=13983816$

如同排列，上面的例子是建立在取出元素不重複出現狀況。

從$n$個元素取出$k$個元素，$k$個元素可以重複出現，組合數量為：

$H_{k}^{n}=C_{k}^{n+k-1}$

以取色球為例，每種顏色的球有無限多顆，從8種色球取出5顆球，這組合數量為：

$H_{5}^{8}=C_{5}^{8+5-1}=C_{5}^{12}={\frac {12!}{5!7!}}=792$

因為組合數量公式特性，重複組合轉換成組合有另一種公式為：

$H_{k}^{n}=C_{k}^{n+k-1}={\frac {(n+k-1)!}{k!(n-1)!}}=C_{n-1}^{n+k-1}$

另外$H_{k}^{n}$也可以記為$F_{k}^{n}$

$F_{k}^{n}=H_{k}^{n}$

總結

$n$中取$k$	直線排列 （考慮順序）	環狀排列	組合 （不考慮順序）
不重複出現 （不放回去）	$P_{k}^{n}={\frac {n!}{(n-k)!}}$ （OEIS數列A008279）	${\frac {n!}{k\cdot (n-k)!}}$ （OEIS數列A111492）	$C_{k}^{n}={\frac {n!}{k!\cdot (n-k)!}}$ （OEIS數列A007318）
可重複出現 （再放回去）	$U_{k}^{n}=n^{k}$ （OEIS數列A004248）	${\frac {\sum _{r|k}(r\cdot \varphi (r)\cdot n^{\frac {k}{r}})}{k}}$ （OEIS數列A075195）	$H_{k}^{n}={\frac {(n+k-1)!}{k!\cdot (n-1)!}}$ （OEIS數列A097805）

參見

• 階乘
• 階乘符號
• 排列
• 組合
• 組合優化

外部連結

• The Combinatorics Net （頁面存檔備份，存於互聯網檔案館）
• Electronic Journal of Combinatorics （頁面存檔備份，存於互聯網檔案館）
• 點算的奧秘 （頁面存檔備份，存於互聯網檔案館）