组合数学

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數有關的枚舉問題[1][2]；西元前3世紀的阿基米德在其數學文章Ostomachion中考慮了一個拼接拼圖的智力遊戲（tiling puzzle）。

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

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

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

• 計算一些物品在特定條件下分組的方法數目。這些是關於排列、組合和整數分拆的。
• 地图着色问题：对世界地图着色，每一個国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？這是圖論的問題。
• 船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？這是線性規劃的問題。
• 中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。這也是圖論的問題。
• 任务分配问题（也称分配问题）：有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？這是線性規劃的問題。
• 如何構造幻方。 幻方為一方陣，填入不重複之自然數，並使其中每一縱列、橫列、對角線內數字之總和皆相同。

从${\displaystyle n}$个元素中取出${\displaystyle k}$个元素，${\displaystyle k}$个元素的排列數量為：

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

以賽馬為例，有8匹马参加比赛，玩家需要在彩票上填入前三胜出的马匹的号码，從8匹馬中取出3匹馬來排前3名，排列數量為：

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

因为一共存在336种可能性，因此玩家在一次填入中中奖的概率应该是：

${\displaystyle P={\frac {1}{336}}=0.00298}$

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

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

從${\displaystyle n}$个元素中取出${\displaystyle k}$个元素，${\displaystyle k}$个元素可以重复出现，這排列數量為：

${\displaystyle U_{k}^{n}=n^{k}}$[10]

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

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

这时的一次性添入中奖的概率就应该是：

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

和排列不同的是，组合取出元素的顺序不考虑。

从${\displaystyle n}$个元素中取出${\displaystyle k}$个元素，${\displaystyle k}$个元素的组合數量为：

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

不過，中國大陸的教科書則是把從n取k的情況記作${\displaystyle C_{n}^{k}}$[11]。

以六合彩為例。在六合彩中从49顆球中取出6顆球的组合數量为：

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

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

从${\displaystyle n}$个元素中取出${\displaystyle k}$个元素，${\displaystyle k}$個元素可以重複出現，這组合數量为：

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

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

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

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

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

另外${\displaystyle H_{k}^{n}}$也可以記為${\displaystyle F_{k}^{n}}$[12]

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

• 阶乘
• 阶乘符号
• 排列
• 组合

• The Combinatorics Net
• Electronic Journal of Combinatorics
• 点算的奥秘