组合数学

维库，知识与思想的自由文库

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

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

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

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

[编辑] 排列

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

排列的任务是确定 $n$ 个不同的元素的排序的可能性。从右边的示意图可看出，3 个不同颜色的彩球一共有 6 种不同的排列方式，因此有如下定理：

   $n$  个不同的元素可以有  $n!$  种不同的排列方式，即  $n$  的阶乘。

因此上面的例子的算法是 3 ! = 6
另一个问题，如果从 $n$ 个元素中取出 $k$ 个元素，这 $k$ 个元素的排列是多少呢？公式如下：

$\frac{n!}{(n-k)!}$

例如，在赌马游戏中一共有 8 匹马参加比赛，玩家需要在彩票上添入前三位胜出的马匹的号码，按照上面的公式， $n$ ＝ 8， $k$ ＝ 3，玩家一共可以添出的 3 匹马号的排列数为：
$\frac{n!}{(n-k)!} =\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$ 个元素可能出现的组合数为：

${n \choose k}$

最常见的例子应该是六合彩游戏了。在六合彩游戏中从 49 个球中取出 6 个进行组合的可能性一共有：
${49 \choose 6}=13983816$ ( 算法见二項式係數 )

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

${n+k-1 \choose k}$

类似的例子比如连续掷两次色子，获得的两个点数的组合可能性一共有：
${6+2-1 \choose 2}=21$

[编辑] 总结

	排列 { a,b } ≠ { b,a }	组合 { a,b } = { b,a }
不重复出现 ( 不放回去 ) { a，b，c }	$\frac{n!}{ \left( n-k \right) !}$	${n \choose k}$
重复出现 ( 再放回去 ) { a，a，b }	$n^k \,$	${n + k - 1 \choose k}$