组合数学

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

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

目录

• 1 组合数学中的著名问题
• 2 排列
• 3 组合
• 4 总结
• 5 外部連結

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

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

[编辑] 排列

主条目：排列

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

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

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

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

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

n^k，

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

8³ = 512

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

（当然，同一匹马同时获得1，2，3名的情况在现实中是不存在的）

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

小结

1. 全排列 :            n!

2. 从n中挑选k个排列： 

3. k如果重复:          n^k

4. e.g: 二进制，x位的二进制有2^x种排列方式，也即可以表达2^x个不同的数字。既从1,0两个数字中挑选x次，可以重复。

[编辑] 组合

主条目：組合

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

最常见的例子应该是六合彩游戏了。在六合彩游戏中从49个球中取出6个进行组合的可能性一共有：

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

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

[编辑] 总结

[编辑] 外部連結

• The Combinatorics Net
• Electronic Journal of Combinatorics
• 点算的奥秘