组合数学

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

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

组合数学中的著名问题

计算一些物品在特定条件下分组的方法数目。这些是关于排列、组合和整数分拆的。
地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。
船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？这是线性规划的问题。
中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个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 = 1 / 336 = 0.00298

以上提到的都是在 $k$ 不发生重复的情况下的排列。如果在 $n$ 个元素中取出 $k$ 个元素进行排列，这 $k$ 个元素可以重复出现，那么排列数则有如下公式：

$n^k \,$

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

8³ = 512

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

P = 1 / 512 = 0.002

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

重复出现的排列或组合

主条目：组合

和排列不同的是，在组合中取出元素的顺序则不在考虑之中。从 $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$

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

$H_k^n = C_k^{n+k-1} = {n+k-1 \choose k}$

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

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

	排列 { a,b } ≠ { b,a }	组合 { a,b } = { b,a }
不重复出现 ( 不放回去 ) { a，b，c }	$P_k^n$	$C_k^n$
重复出现 ( 再放回去 ) { a，a，b }	$n^k \,$	$H_k^n$

Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History