组合数学

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

组合数学中的著名问题[编辑]

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

排列[编辑]

n个元素中取出k个元素,k个元素的排列數量為:

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

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

 P_3^8 =\frac{8!}{(8-3)!}=336

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

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

不過,中國大陸的教科書則是把從n取k的情況記作P^k_nA^k_n(A代表Arrangement,即排列)。

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

n个元素中取出k个元素,k个元素可以重复出现,這排列數量為:

 U_k^n = n^k[1]

四星彩為例,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)!}

六合彩為例。在六合彩中从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[2]

F_k^n = H_k^n

总结[编辑]

直線排列
(考慮順序)
环状排列 组合
(不考慮順序)
不重复出现
(不放回去)
P^n_k
OEIS中的数列A008279
OEIS中的数列A111492 C^n_k
OEIS中的数列A007318
重复出现
(再放回去)
U^n_k
OEIS中的数列A004248
OEIS中的数列A075195 H^n_k
OEIS中的数列A097805

参见[编辑]

參考文獻[编辑]

  1. ^ 組合數學 ─算法與分析─. 九章出版社. : 29.  OCLC:44527392
  2. ^ 組合數學 ─算法與分析─. 九章出版社. : 33.  OCLC:44527392

外部連結[编辑]