组合数学

组合数学（Template:Lang-en），在总體上是一门研究可數或离散对象的科学。它可分为廣義上的和狭義上的兩種層面，若是前者 (廣義的组合数学) ，其相当于离散数学，而后者 (狭义的组合数学) 則是组合计数、图论、代数结构、数理逻辑等的总称，但这只是不同学者在稱謂上的区别。而随着计算机科学日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。

狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计(Template:Link-en)、组合矩阵(Template:Link-en)、组合最佳化（最佳組合）等。

歷史

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

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

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

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

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

组合数学中的著名问题

• 計算一些物品在特定條件下分組的方法數目。這些是關於排列、組合和整數分拆。
• 地图着色问题：為地图填色，每區用一色。如果要邻區颜色相异，是否只需四色？這是圖論題。
• 船夫过河问题：船夫要把一匹狼、一只羊和一棵菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊，但船每次只能运送一种东西。怎样把所有东西运过河？這是線性規劃題。
• 中国邮差问题：由中华民国组合数学家管梅谷教授提出。邮差要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。也是圖論題。
• 任务分配问题（也称分配问题）：有一些员工要完成一些任务。各员工完成不同任务用的时间都不同。每个员工只分配一项任务。每项任务只分给一个员工。怎样分配员工与任务以使所花费的时间最少？也是線性規劃題。
• 如何構造幻方： 幻方為一方陣，填入不重複之自然數，並使其中每一縱列、橫列、對角線內數字之和皆相同。
• 數獨：遊戲一般由9個3×3個的九宫格組成。每一列的數字均須包含 1～9，不能缺少，也不能重複。每一宮(粗黑線圍起來的區域，通常是 3x3 的九宮格)的數字均須包含 1～9，不能缺少，也不能重複。^{參見Template:Link-en}

排列

Template:Main 从$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$

组合

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

从$n$个元素取出$k$个，$k$个元素的组合數量为：

$C_k^n=(\genfrac{}{}{0ex}{}{n}{k})=\frac{P_k^n}{k!}=\frac{n!}{k!(n-k)!}$

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

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

$C_6^{49}=(\genfrac{}{}{0ex}{}{49}{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)!}$ Template:OEIS	$\frac{n!}{k\cdot (n-k)!}$ Template:OEIS	$C_k^n=\frac{n!}{k!\cdot (n-k)!}$ Template:OEIS
可重复出现 （再放回去）	$U_k^n=n^k$ Template:OEIS	$\frac{\sum _{r|k}(r\cdot \phi (r)\cdot n^{\frac{k}{r}})}{k}$ Template:OEIS	$H_k^n=\frac{(n+k-1)!}{k!\cdot (n-1)!}$ Template:OEIS

参见

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

外部連結

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