dvrgv

本条目需要編修，以確保文法、用詞、语气、格式、標點等使用恰当。（2012年12月7日） 請按照校對指引，幫助编辑這個條目。（幫助、討論）

广义的组合数学（英语：Combinatorics）就是离散数学，狭义的组合数学是组合计数、图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究可數或离散对象的科学。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。

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

组合数学中的著名问题

• 計算一些物品在特定條件下分組的方法數目。這些是關於排列、組合和整數分拆的。


• 
  地图着色问题：对世界地图着色，每一個国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？這是圖論的問題。


• 
  船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？這是線性規劃的問題。


• 
  中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。這也是圖論的問題。


• 
  任务分配问题（也称分配问题）：有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？這是線性規劃的問題。


• 如何構造幻方。 幻方為一方陣，填入不重複之自然數，並使其中每一縱列、橫列、對角線內數字之總和皆相同。

排列

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

Pkn=n!(n−k)!{displaystyle P_{k}^{n}={frac {n!}{(n-k)!}}}

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

P38=8!(8−3)!=8×7×6=336{displaystyle P_{3}^{8}={frac {8!}{(8-3)!}}=8times 7times 6=336}

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

P=1336=0.00298{displaystyle P={frac {1}{336}}=0.00298}

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

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

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

Ukn=nk{displaystyle U_{k}^{n}=n^{k}}^[1]

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

U410=104=10000{displaystyle U_{4}^{10}=10^{4}=10000}

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

P=110000=0.0001{displaystyle P={frac {1}{10000}}=0.0001}

组合

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

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

Ckn=(nk)=Pknk!=n!k!(n−k)!{displaystyle C_{k}^{n}={n choose k}={frac {P_{k}^{n}}{k!}}={frac {n!}{k!(n-k)!}}}

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

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

C649=(496)=49!6!43!=13983816{displaystyle C_{6}^{49}={49 choose 6}={frac {49!}{6!43!}}=13983816}

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

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

Hkn=Ckn+k−1{displaystyle H_{k}^{n}=C_{k}^{n+k-1}}

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

H58=C58+5−1=C512=12!5!7!=792{displaystyle H_{5}^{8}=C_{5}^{8+5-1}=C_{5}^{12}={frac {12!}{5!7!}}=792}

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

Hkn=Ckn+k−1=(n+k−1)!k!(n−1)!=Cn−1n+k−1{displaystyle H_{k}^{n}=C_{k}^{n+k-1}={frac {(n+k-1)!}{k!(n-1)!}}=C_{n-1}^{n+k-1}}

另外Hkn{displaystyle H_{k}^{n}}也可以記為Fkn{displaystyle F_{k}^{n}}^[2]

Fkn=Hkn{displaystyle F_{k}^{n}=H_{k}^{n}}

总结

n{displaystyle n}中取k{displaystyle k}	直線排列 （考慮順序）	环状排列	组合 （不考慮順序）
不重复出现 （不放回去）	Pkn=n!(n−k)!{displaystyle P_{k}^{n}={frac {n!}{(n-k)!}}} （OEIS中的数列A008279）	n!k⋅(n−k)!{displaystyle {frac {n!}{kcdot (n-k)!}}} （OEIS中的数列A111492）	Ckn=n!k!⋅(n−k)!{displaystyle C_{k}^{n}={frac {n!}{k!cdot (n-k)!}}} （OEIS中的数列A007318）
可重复出现 （再放回去）	Ukn=nk{displaystyle U_{k}^{n}=n^{k}} （OEIS中的数列A004248）	∑r|k(r⋅φ(r)⋅nkr)k{displaystyle {frac {sum _{r|k}(rcdot varphi (r)cdot n^{frac {k}{r}})}{k}}} （OEIS中的数列A075195）	Hkn=(n+k−1)!k!⋅(n−1)!{displaystyle H_{k}^{n}={frac {(n+k-1)!}{k!cdot (n-1)!}}} （OEIS中的数列A097805）

参见

• 阶乘


• 阶乘符号


• 排列

參考文獻

外部連結

• The Combinatorics Net


• Electronic Journal of Combinatorics


• 点算的奥秘