组合数学

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

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

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

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

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

排列[编辑]

3个彩球的排列(不重复出现)

排列的任务是确定n个不同的元素的排序的可能性。从右边的示意图可看出,3个不同颜色的彩球一共有6种不同的排列方式,因此有如下定理:n个不同的元素可以有n !种不同的排列方式,即n阶乘。」[來源請求]因此上面的例子的算法是3 ! = 6。
另一个问题,如果从n个元素中取出k个元素,这k个元素的排列是多少呢?公式如下:

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

例如,在赌马游戏中一共有8匹马参加比赛,玩家需要在彩票上填入前三位胜出的马匹的号码,按照上面的公式,n = 8,k = 3,玩家一共可以填出的3匹马号的排列数为:

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

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

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

以上提到的都是在k不发生重复的情况下的排列。

如果在n个元素中取出k个元素进行排列,这k个元素可以重复出现,那么排列数则有如下公式:

n^k

还是上面的例子,k可以重复出现,这意味着玩家可以在前三名的位置上填入同一匹马号,因此在这种情况下可能出现的排列总数为:

83 = 512

另外,n^k也可以記為[1]

 U_n^k = n^k[1]

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

P=\frac{1}{512}=0.002(当然,同一匹马同时获得1,2,3名的情况在现实中是不存在的)

另一个来自数字技术的例子,在二进制中只有0和1两种状态,一个有x位的二进制数字可以有2x种排列方式,也即可以表达2x个不同的数字。

组合[编辑]

和排列不同的是,在组合中取出元素的顺序则不在考虑之中。从n个元素中取出m个元素,这m个元素可能出现的组合数为:

C_m^n ={n \choose m} = \frac{P_m^n}{m!} = \frac{n!}{m!(n-m)!}

六合彩游戏為例。在六合彩游戏中从49个球中取出6个进行组合的可能性一共有:

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

如同排列,上面的例子是建立在如下前提的(即球从摇奖机中出来后不再放回去,或者说组合不发生重复),但如果球摇出来后再放回摇奖机中,这时的组合的可能性则是:

H_m^n = C_{m}^{n+m-1} = {n+m-1 \choose m}

类似的例子比如连续掷两次骰子,获得的两个点数的组合可能性一共有:

H_2^6 = C_{2}^{6+2-1} = {6+2-1 \choose 2} = C_2^7 = \frac{7!}{2!5!} = 21

值得一提的是,方程式a_1+a_2+a_3+\dots+a_n=m 的非負整數解之個數亦可由此解答。 此問題可視為「n個1和n-1個加號」的排列,故解的個數為 H_m^n=C_{n-1}^{m+n-1}

另外H_r^n也可以記為[2]

F_r^n = H_r^n = C_{r}^{n+r-1} = {n+r-1 \choose r}[2]

总结[编辑]

排列
{ a,b } ≠ { b,a }
(考慮順序)
组合
{ a,b } = { b,a }
(不考慮順序)
不重复出现(不放回去)
{ a,b,c }
{P}^n_r {C}^n_r
重复出现(再放回去)
{ a,a,b }
n^k \, {H}^n_r

参见[编辑]

參考文獻[编辑]

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

外部連結[编辑]