《复旦大学计算机科学与工程系_吴永辉_离散数学_组合数学》由会员分享，可在线阅读，更多相关《复旦大学计算机科学与工程系_吴永辉_离散数学_组合数学（60页珍藏版）》请在金锄头文库上搜索。
1、组合数学初步第十章 鸽笼原理第十一章 排列与组合第十二章 生成函数与递推关系组合数学/组合论组合数学/组合论：应用数学学科，对于算法 研究变得日益重要。计算机算法分类数值计算：方程组求解、积分计算非数值计算：搜索、排序、组合优化（主要 是组合算法）设计和分析组合算法的基础是组合数学组合数学的四个方面判定所提出问题的解是否存在的存在性问题确定有解问题其不同解的个数的计数问题对可解问题去把解构造出来的构造性算法从问题的多种构造性算法中择优改进的优化 问题。讲授内容组合数学中的存在性问题和计数问题组合数学经典教材组合数学（第3版），卢开澄，卢华明著 ，清华大学出版社。（有课件，可拷贝）组合数学（英文
2、版.第3版），（美） Richard A. Brualdi，译者：冯舜玺、罗平、 裴伟东。校：卢开澄、冯舜玺。Prentice Hall ，机械工业出版社。组合数学一、组合数学的历史和发展原因二、组合数学两类一般性问题三、组合学另外两种问题四、组合数学的定义一、组合数学的历史和发展原因1. 组合数学的历史渊源扎根于数学娱乐和游 戏之中。2. 组合数学的历史和发展原因1) 计算机的发展, 程序的基础往往是求解 问题的组合学算法.2) 组合数学对于过去很少与数学正式接 触的学科的适用性二、组合数学两类一般性问题组合数学涉及将一个集合的物体排列成满足 一些指定规则的格式。1.排列的存在性: 排列在什
3、么样的(充分和必要 )条件下能够实现?2.排列的计数和分类: 如果一个排列是可能的, 那么就会存在多种方法实现它. 此时, 就可以 计数并将它们分类.组合学问题形式：能否排列?存在一个吗?能用多少方法?计算的数目.三、组合学另外两种问题研究一个已知的排列构造一个最优的排列四、组合数学的定义组合数学是研究离散结构的存在、计数、分 析和优化等问题的一门学科。第十章 鸽笼原理10.1 鸽笼原理的简单形式10.2 鸽笼原理的加强形式10.1 鸽笼原理的简单形式1, 问题的引入实例：某次会议有n位代表参加，每位代表认识 其他代表中某些人，则至少有两个人认识的 人数是一样的。10.1 鸽笼原理的简单形式2
4、, 鸽笼定理10.1 n+1只鸽子飞回n个笼子，至少有一个鸽 笼含有不少于2只鸽子。 证明方法：反证证明方法：反证 例 例 367367人中至少有人的生日相同。人中至少有人的生日相同。 例 例 1010双手套中任取双手套中任取1111只，其中至少有两只，其中至少有两 只是完整配对的。只是完整配对的。3, 鸽笼的扩展（抽象）定理10.2 s（s1）个元素分成t个组，那么必存在 一个组至少含有s/t（这里 为“上整数”记号 ）个元素。 证明方法：反证法证明方法：反证法。证明：若每个组至多含有(s/t-1)元素，则t个 组共有元素t(s/t-1)，因为s/t s/t|R| ，令i= |D|/ |R|
5、，则D中存在i个元素d1, d2, , di，使得f(d1)=f(d2)=f(di)。证明方法：此问题相当于定理10.2，把|D|个 元素分到|R|个组中去。证明：在这|R|个组中有一个组至少含有i= |D|/ |R|个元素。在同一组中对应的函数值 是相等的。所以在D中至少存在i个元素d1, d2, , di，使得f(d1)=f(d2)= f(di) 。2）例10.2 在n+1个小于或等于2n的互不相 等的正整数中，必存在两个互质的数。证明：把1, 2, , 2n这2n个数分成n个组： 1, 2, 3, 4, , 2n-1, 2n；则问题归结为 从n个组中取n+1个数，由定理10.1知，至少
6、有2个数取自同一组，由于这两个数是相邻的 正整数，故互质。3）例10.3 1, 2, , 2n中任取n+1个互不 相同的数中，必存在两个数，其中一个数是 另一个数的倍数。证明：因为任何正整数n可以表示成 n=2ab（这里a=0, 1, 2,，且b为奇数 ）。设取出的n+1个数为k1, k2, , kn+1， 则ki=2aibi。由于b1, b2, , bn+1是奇数，共有 n+1个，而在1, 2, , 2n中只有n个不 同的奇数，所以必存在i, j，使得bi=bj。不妨设kikj，则有ki / kj =2ai-aj为正 整数，因此ki是kj的倍数。4）例10.4 一个国际象棋选手为参加国际比
7、赛，突击训练77天，要求每天至少下一盘棋 ，每周至多下12盘棋。证明：无论如何安排总可以使他在这77天里 有连续几天共下21盘棋。证明：用ai表示从第1天到第i天下棋的总盘数 （i=1, 2, , 77）。由于规定每天至少下一盘 棋，每周至多下12盘棋，所以 1a1100-1 ，所以，由推论10.2，某个位置,使得小盘上 至少有100个小段与大盘上对应段颜色相同。习题解析鸽笼原理用于判断是否存在满足鸽笼原理条件的对象 ，若鸽笼原理的条件成立，则存在满足条件 的对象。运用鸽笼原理时必须确定哪些对象相当于鸽 子，而哪些对象相当于鸽笼。鸽笼原理形式设函数f是从有限集X到有限集Y的映射，且 |X|Y|
8、，则必存在x1, x2X，x1x2，满足 f(x1)=f(x2)。鸽笼原理形式例题1. 20个处理器连成网络，证明至少有两个处 理器与相同数目的处理器直接相连。 解题分析：解题分析： 20个处理器编号分别为1, 2, 3, , 20，（ 定义域X=1, 2, 3, 20）；ai表示与第i个 处理器直接相连的处理器的数目（f(X)）。证明：对于某两个i, j，ij，ai=aj。解：X=1, 2, 3, 20, Y=0, 1, 2, 19; 0和 19不能同时作为函数值存在，即不存在两个i, j，ij，ai=0，aj=19。所以|X|=20, |Y|20。根据鸽笼原理形式1，命题成立。2. 列表中
9、有80件物品，每个物品的属性为“ 可用”或“不可用”，共有45个“可用”的物品， 证明至少有两件可用物品的编号差恰为9。 解题分析：解题分析：ai表示第i个可用物品的编号；证明：对于某两个i, j，ij，ai-aj=9。证明：考虑下列两组数字： a1, a2, , a45 a1+9, a2+9, , a45+9 这两组共90个数字，取值范围为1-89。因为第一组数字两两不同，第二组数字也 是两两不同，所以必存在两个i, j，ij，ai- aj=9。习题解析10.1 在边长为2的正三角形中任意放置5个点 , 证明至少有两个点之间的距离不大于1.解题要点：确定鸽子和鸽笼/*将三角形分成边长为1的4
10、个正三角形*/10.4 将一个圆盘分为36段，将1, 2, , 36这36个数字任意标在每一段上，使得每一 段恰有一个数字。证明：必存在相继的3段， 它们的数字之和不小于56。证明：设36个小扇形分别为a1, a2, , a36。ai 中放的数为xi，i=1, 2, , 36。1 xi 36，且 当时ij，xixj。将36个小扇形合并成12个大 扇形：A1=a1a2a3, A2=a4a5a6, , A12=a34a35a36 ，并设Aj中3数之和为yj，j=1, 2, , 12。则将1837个元素分配给12个扇形，由鸽巢原 理，至少存在一个扇形，分配给它的元素个 数至少是 1837 / 12=
11、56。所以命题成立。例 设 a1, a2, a3为任意个整数，b1 ，b2, b3 为a1, a2, a3的任一排列，则 a1-b1, a2-b2, a3- b3中至少有一个是偶数证明: 由鸽巢原理， a1, a2, a3为任意个整 数，设这个数被除的余数为 xxy，于是b1，b2, b3 中被除的余数有个x，一个y这 样a1-b1, a2-b2, a3- b3被除的余数必有一个 为10.3 证明: 对于任意正整数N, 必存在N的一 个倍数,使得它仅由数字0和7组成.作业：10.1, 10.2, 10.5, 10.6鸽笼原理形式习题1）5台处理器连成网络，恰有两台与相同数 量的处理器相连，可能吗？2）列表中有100件物品，每个物品的属性为“ 可用”或“不可用”，共有55个“可用”的物品， 证明至少有两件可用物品的编号差恰为4。3）列表中有80件物品，每个物品的属性为“ 可用”或“不可用”，共有50个“可用”的物品， 证明至少有两件不可用物品的编号差恰为3或 6。
