组合数学课件：第一章 引言

1、组合数学Combinatorics关于这门课定位：专业基础课性质：组合数学在计算机科学中的应用预备知识：离散数学等后续课程：算法分析、人工智能、可计算性与计算复杂性等目的：掌握计算机科学的数学基础，程序设计比赛、工作面试等常涉及到2参考书(1)Richard A.Brualdi. Introductory Combinatorics，Fifth Edition ，Prentice Hall, 2012. （冯速 ：译 .机械工业出版社 ，2012 年5月）3参考书(2)卢开澄，卢华明.组合数学(第四版)，清华大学出版社，2006.Fred S.Roberts, Barry Tesman. Ap

2、plied Combinatorics, Prentice Hall, 2007.(冯速：译，应用组合数学（第二版），机械工业出版社，2007)4计算一些物品在特定条件下分组的方法数目。这些是关于排列、组合和整数分拆的。 地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论问题。 中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论问题。 如何构造

3、幻方。 5组合数学中的著名问题组合数学的起源幻方最早记载于我国公元前500年的春秋时期大戴礼中，这说明我国人民早在2500年前就已经知道了幻方的排列规律。而在国外，公元130年，希腊人塞翁才第一次提起幻方 公元1275年（宋代），杨辉的著作中出现10阶幻方问题和杨辉三角的记载1666年，莱布尼茨发表组合的艺术(De Art Combinatoria)，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。标志组合数学的诞生67引言组合数学(简称组合学）是数学的一个分支, 它起源于古代的娱乐和休闲游戏。后来这些问题逐渐与数论、概率统计、拓扑学、线性规划等学科的问题交织

4、在一起，逐渐形成一种理论。应用领域：通信、运输、生物、汽车制造核心问题：将一些物体安排成满足一定规则的模式或形态8 组合数学的蓬勃发展则是在计算机问世和普遍应用之后。当组合问题规模很大的时候，计算量很大，计算机为求解这些问题提供了有力手段。在计算机科学的算法研究中, 要进行算法的时间复杂性和空间复杂性分析，要用到组合数学的知识，因此，组合数学理论有为计算机的算法设计和分析提供理论支持。组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科。组合数学就是研究按照一定的规则来安排一些离散个体的问题。它涉及面广，内容庞杂（涉及到组合分析、图论、组合算法、近代密码学、编码理论等），并且仍在很快

5、地发展着，因而还没有一个统一而有效的理论体系。 研究的对象是离散结构，一般可以用1，2，n表示。本书仅限于讨论n是有限的自然数的情况。9什么是组合数学组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换（一一对应）。学好组合数学既需要一定的数学修养，也要进行相当的训练。可从规模小的模型着手，从中找到规律性的东西，再推及一般。你解决的问题越多，那么你能够解决下一个问题的可能性也越大。 10组合数学的学习特点11 组合数学研究的主要问题（1）存在性问题满足一定条件的安排的存在性. 如果某种安排不一定总存在，我们就需要研究存在的条件。 存在性是数学研究最重要的问题之一.

6、 许多问题的存在性至今也无法解决？ 例如数论中很多难题：哥德巴赫猜想 （2）安排的枚举、分类和计数 如果所要求的安排存在，则可能有多种不同的安排。此时，需要计数不同的方案数，并将它们进行枚举和分类。 当实际问题比较复杂的时候，必须有好的方法来解决.12 （3）构造性问题 一个组合问题，如果已经判定解是存在的，那么将所有可能的安排构造出来是一个关键问题。 与计算机算法密切相关，典型问题：组合设计13 （4）优化问题在给定的优化条件下从所有的安排方案中找出最优的安排方案。 如最短路径问题、数学规划问题，与算法分析密切相关14本课程涉及的内容：(不含图论和组合设计)鸽巢原理和Ramsey定理（存在性

7、问题）基本计数方法容斥原理生成函数递推关系Plya定理15组合计数问题排列和组合的生成、Polya定理的生成函数形式为构造问题。16幻方问题有趣的数学游戏 幻方在娱乐数学中的地位以及它的意义非同一般，它是中国人的首创。 1.1 幻方问题(Magic square)一个n阶幻方是由整数1，2，3，n2按下述方式组成的nn方阵：该方阵每行上的整数的和、每列上的整数的和以及两条对角线中每条对角线上的整数的和都等于同一个数S 17 3阶幻方的所有整数和为15；每一行（或列或对角线）数字的和称为幻方的和（幻和）： S= n (n2+1)/2 。关于幻方的问题归结为:（一）存在性问题 对任意的正整数n，n

8、阶幻方存在吗？（二）组合计数问题 如果存在，那么应该有多少个不同的 n阶幻方。 （三）构造问题 奇数阶幻方：连续摆数法(de La Loubre法) 双偶数（4k）阶幻方：对称法 单偶数(4k+2)阶幻方：斯特雷奇法（1918） 1819（一）幻方的存在性问题 例1.1 证明了不存在2阶幻方。对其余的正整数n，由于n阶幻方都能构造出来，当然就证明了（正整数）阶幻方的存在性。 20例 1.1 证明不存在2阶幻方。证明：反证法。假定存在2阶幻方，如图所示：a1a2a3a4根据幻方的定义，它的幻和是5，于是a1+ a2= a1+ a3=5，可得a2= a3，因为a1，a2，a3， a4必定彼此不同，

9、所以不可能，矛盾。因此不存在2阶幻方。 21（二） 幻方的构造性问题（1）奇数阶幻方的构造连续摆放法（de la Loubre法）。规则为：假定构造n阶（n为奇数）幻方。 首先将1放在(n+1)/2列第1行的方格中， 然后按照副对角线方向（即行号减1，列号加1）依次把从小到大的各个数字放入相应的方格中。22 如果行号变成0（第1行上面一行），则改成第n行相应列对应的方格。 如果列号变成n+1（第n列右面一列），则改成第1列相应行对应的方格。 如果轮到的方格已经填有数字或者到了第0行第n+1列对应的方格，则退到前一个方格正下方的方格。 例1.2 利用连续摆放法构造5阶幻方/p>

10、7141646132022101219213111825292324（2）偶数阶幻方的构造 当n=4k的时候，即双偶数的情况，对称法。先把nn的方阵分成上、下、左、右四个2k2k的方阵。然后对于左上的2k2k方阵进行处理，每行每列任意取一半（k个）的方格做标记，如我们把这些方格涂成阴影。25 然后按照对称轴将这种标记方式向下和向右作对称图形。经过处理后使得nn的方阵的每一行和每一列都有一半（n/2）的方格被涂成阴影。 接下来，把从1开始的数字依次往方格里面填。第一遍：从第1行第1列的方格开始往右，不是阴影，则填数字，如果是阴影的方格，不填数字，但相应的数字加1。第1行填完后，是第2行第1列的方

11、格，依次，最后是第n行第n列的方格。26 这样填完之后，有一半的方格被填上了数字。 第二遍，从第n行第n列的方格开始依次往左，规则同前，从1开始的数字依次往方格里面填。第n行结束之后，是第n-1行第n列的方格。依次，最后是第1行第1列的方格。 最后就得到了幻方。27 例1.3 利用对称法构造4阶幻方 214315812592117143106151381211659428 当n=4k+2,所谓的单偶数的情况。 首先把nn的方阵分成上、下、左、右四个(2k+1)(2k+1)的方阵,为了表达方便，依次把左上、右下、右上、左下的方阵编号为A,B,C,D。 采用连续摆数法，把1(2k+1)2放在A中做

12、成第一个幻方；把(2k+1)2 12(2k+1)2放在B中成第二个幻方。29 把2(2k+1)213(2k+1)2放在C中成第三个幻方。 把3(2k+1)214(2k+1)2放在D中成第四个幻方。 然后，在A的各行从第1列开始向右取k个(k=(n-2)/4)方格，但中间一行（k+1行）从第2列开始。30 把这些方格中的数字与D中相应位置的数字对换。 在C中各行最后一列右起向左各取k1个方格，把这些方格中的数字与B中相应位置的数字对换。最后，就得到了幻方。31例1.4 构造6阶幻方 159283267233342621221712192327101483435303629131831242520

13、151611ABCD32132928567233342621221712192327101435331830362913184242520151611ABCD33（三）幻方的计数问题 3阶幻方 基本形式只有一种 经过旋转和翻转可获得8种变形 4阶幻方 分类枚举 基本形式有880个 变形有7040个34 5 阶幻方基本形式有275305224个 6 阶及以上幻方即使通过大型计算机的计算仍然难以获得精确的数字，目前只能估计出它的取值范围三维幻方（幻方体，magic cube）351.2 拉丁方问题（Latin square） 拉丁方是另一类典型的组合数学问题 n阶拉丁方定义为由数字1,2,n构成的

14、nn的方阵，使得在每1行、每1列中每个数字都恰好出现1次。 36拉丁方存在性问题 2阶拉丁方是存在的 122137n阶拉丁方是存在的 构造方法如下：第1行为（1,2,3,n）第2行是(2,3,n,1)，第k行为(k,k+1,n,1, ,k-1)，第n行为（n,3, 2, 1）。 数独的解是满足限定条件的9阶拉丁方。38 例1.5 设计一个药物临床试验以测试五种药物对人体的药效。这五种药物编号1,2,3,4,5。然后选取5个人，并给每人不同的药。为了消除个体对药物的反应偏差，要求在连续5天里进行测试，每人每天吃一种药物。而为了消除服药时间造成药效的偏差，要求2个人不能在同1 天吃相同的药。 39

15、最后满足要求的实验是要形成由1,2,3,4,5构成的55的方阵，其中每行每列中没有相同的数字，即5阶拉丁方的构造问题。402345134512451235123412345例 36军官问题 有36名军官来自六个不同的团，具有六种不同的军衔，而且每个团每种军衔的军官各有一名，能否把他们排成一个66方阵，使得对每一个团与每一种军衔，在每一行或每一列都有一位军官来自这个团，也都有一位军官有此军衔？是由Euler首先提出的，实际上是组合设计中的正交拉丁方问题，属于构造问题。41如果每一个军官用一个有序对(i,j)来表示,其中i表示它们的军衔类别(i=1,6),而j表示他所在的团(j=1,2, 6),于

16、是问题即要求将有序对(i, j) (i=1,2,6；j=1,2,6)排成一个66数组，使得每一行或每一列中整数1,2,6中任一数以某种次序出现于有序对的第一位置，又以另一种次序（不一定相同）出现于有序对的第二位置.42分别考虑军衔方阵与团队方阵, 于是问题就是是否存在两个66数组满足： (1) 每个数组中每一行或每一列中整数 1,2,6以某种次序出现; (2) 两个数组并置时, 所有的36个有序对 (i,j) (i=1,2,6; j=1,2,6)都将出现. 满足第一个条件的每个方阵称为拉丁方，满足第二个条件的两个拉丁方称为互相正交，即正交拉丁方. 4344上述是两个3阶正交拉丁方。 36军官问

17、题即是否存在6阶正交拉丁方。n为奇数和n=4k（欧拉），n=4k+2,k11960年由三位数学家给出，但无6阶正交拉丁方（欧拉猜想，1901年证明） 对于只有9个军官的类似问题有解：451.3 涂色问题（Coloring） 在实际应用中，很多计数问题都可抽象成涂色问题。作为典型的组合计数问题，根据涂色问题难度的不同，将反映出各种不同的计数技术。46例1.6 对正三角形的三个顶点涂以红、蓝（r和b）两种颜色，求有多少种不同的涂色方案？ 解 由于只有两种颜色，我们可以采用枚举方法分类讨论。47 涂色方案可分成四类：（1）三点全涂红色，只有一种方案 rrr（2）三点全涂蓝色，只有一种方案 bbb（3

18、）两点涂红色，一点涂蓝色，因蓝色可分别涂于三个顶点之一，故有3种方案 brr，rbr，rrb（4）由对称性可知，两点涂蓝色，一点染红的方案也有3种： 48（1） （2） （3） （4）（5） （6） （7） （8）49 如果考虑正三角形可以旋转，则(3),(4),(5)显然是同一个涂色方案，(6),(7),(8)也是同一个涂色方案，这样涂色方案数就变成了4种。 如果变成了空间的四面体了，即加上空间的旋转之后，涂色方法的计算将更加复杂。 要涂色的点和可选颜色的数目如再增加的话，枚举就很困难了需要特殊技巧解决问题例 有101名选手参加羽毛球比赛，如果采用单循环淘汰制，问产生冠军需要进行多少场比赛？ 方法一：50+25+13+6+3+2+1=100场比