组合数学教学课件.ppt

《组合数学教学课件.ppt》由会员分享，可在线阅读，更多相关《组合数学教学课件.ppt（63页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、南开大学ACM暑期集训之组合数学,朱毅2006年8月,主要参考文献,组合数学讲义任课教师：黄连生 清华大学计算机系,内容提要,排列组合鸽巢原理递推关系与生成函数二分图的最大匹配Polya计数原理的相关数学基础,排列组合,圆排列,6位女士和6位先生围着一张圆桌聚餐，要求安排女士和先生交替就座。问：有多少可能的安排方案。解. 由于要求安排女士和先生交替就座，因此可以先安排六位女士坐下，两位之间留出一个空位，然后再安排先生就座。安排六位女士坐下（圆排列）的方案数是 （种）,圆排列（续）,由于已经有女士在位，安排先生在六个空位上就座时，就不再是圆排列了，因为原先被看成相同圆排列的六位先生的就座方式所产

2、生的全体人员的圆排列是不同的。故安排先生在六个空位上就座的方案数是6！720于是我们得到满足要求安排方案共计有,全排列生成算法,如果将整数n从1，2。，n的一个排列中删除，那么结果则是1，2。，n-1的一个排列。给定一个1，2。，n-1的排列，只要将n插入到其中的n个间隔（含头尾）算法描述：从1开始，将2插入排列中得1，2的排列，以此类推，直至得到1，2。，n的排列,1，2，3全排列生成算法示例,1221 1 2 3 1 3 2 3 1 2 2 1 3 2 3 1 3 2 1,STL中生成排列数的函数,#include int A = 2, 3, 4, 5, 6, 1;prev_permuta

3、tion(A, A+6);结果：234516int A = 2, 3, 4, 5, 6, 1;next_permutation(A, A+6);结果：234615,相关练习,NKOJ 1038NKOJ 1108,鸽巢原理,鸽巢原理之一,鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。即,“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有两个鸽子。”,例367人中至少有人的生日相同。例10双手套中任取11只，其中至少有两只是完整配对的。例参加一会议的人中至少有人认识的别的参加者的人数相等。,鸽巢原理之二,鸽巢原理二m1 , m2 , , mn都是正整数，并有m1 + m2 + +

4、mnn + 1个鸽子住进n个鸽巢，则至少对某个 i 有第 i 个巢中至少有mi个鸽子，i = 1 , 2 , , n,上一小节的鸽巢原理一是这一原理的特殊情况，即m1 = m2 = = mn= 2， m1 + m2 + +mnn + 1 = n + 1如若不然，则对任一 i， 都有第 i 个巢中的鸽子数mi1则,鸽子总数 m1 + m2 + +mnn ，与假设相矛盾,推论m只鸽子进n个巢，至少有一个巢里有 |只鸽子,n,m,推论n(m1) + 1只鸽子进n个巢，至少有一个巢内至少有m只鸽子,递归关系和生成函数,定义：对于序列 构造一函数：,母函数,称函数G(x)是序列 的母函数,递推关系,利用

5、递推关系进行计数这个方法在算法分析中经常用到，举例说明如下：,例一.Hanoi问题：这是个组合数学中的著名问题。N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。,递推关系,Hanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，集估计工作量。,算法：,N=2时,第一步先把最上面的一个圆盘套在B上, ,第二步把下面的一个圆盘移到C上, ,最后把B上的圆盘移到C上,到此转移完毕,递推关系,对于一般n个圆盘的问题，,假定n

6、-1个盘子的转移算法已经确定。,先把上面的n-1个圆盘经过C转移到B。,第二步把A下面一个圆盘移到C上,最后再把B上的n-1个圆盘经过A转移到C上,递推关系,上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。N=4，5，以此类推。,递推关系,算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。 n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有,递推关系,算法复杂度为：

7、,H(x)是序列 的母函数。给定了序列，对应的母函数也确定了。反过来也一样，求得了母函数，对应的序列也就可得而知了。当然，利用递推关系(2-2-1)式也可以依次求得 ，这样的连锁反应关系，叫做递推关系。,递推关系,下面介绍如何从(2-2-1)式求得母函数H(x)的一种形式算法。所谓形式算法说的是假定这些幂级数在作四则运算时，一如有限项的代数式一样。,递推关系,根据(2-2-1)，,或利用递推关系(2-2-1)有,递推关系,上式左端为：,右端第一项为：,右端第二项为：,递推关系,整理得,这两种做法得到的结果是一样的。即：,递推关系,令,如何从母函数得到序列 ？下面介绍一种化为部分分数的算法。,递

8、推关系,由上式可得：,即：,递推关系,因为：,递推关系,例2. 求n位十进制数中出现偶数个5的数的个数。,先从分析n位十进制数出现偶数个5的数的结构入手 是n-1位十进制数，若含有偶数个5，则 取5以外的0，1，2，3，4，6，7，8，9九个数中的一个，若 只有奇数个5，则取 ，使 成为出现偶数个5的十进制数。,递推关系,解法1：,令 位十进制数中出现偶数个5的数的个数， 位十进制数中出现奇数个5的数 的个数。,故有：,也有类似解释。,递推关系,(2-2-2)式中的 表达了含有偶数个5的n位十进制数的两个组成部分。 表达由含有偶数个5的n-1位十进制数 ，令 取5以外的0，1，2，3，4，6，

9、7，8，9九个数中的一个数构成的。 项表示当 是含有奇数个5的n-1位十进制数，令 而得 是含偶数个5的n位十进制数。,(2-2-2)是关于序列 和 的连立关系。,递推关系,设序列 的母函数为 ，序列 的母函数为 。,即：,递推关系,承前页：,递推关系,又：,故得关于母函数 和 得连立方程组：,递推关系,递推关系,递推关系,解法二： n-1位的十进制数的全体共 从中去掉含有偶数个5的数，余下的便是n-1位中含有奇数个5的数。故有：,递推关系,令,递推关系,母函数和递推关系应用举例,例6：设有n条封闭的曲线，两两相交于两点，任意三条封闭曲线不相交于一点。求这样的n条曲线把平面分割成几个部分？ 设

10、满足条件的n条封闭 曲线所分割成的域的数目为 ，其中 条封闭曲线 所分割成的域的数目为,母函数和递推关系应用举例,第n条封闭曲线和这些曲线相交于 个点，这 个点把第n条封闭曲线截成 条弧，每条弧把 个域中的每个域一分为二。故新增加的域数为,利用递推关系 得,母函数和递推关系应用举例,设,母函数和递推关系应用举例,另解：利用欧拉公式 点数+域数-边数=2点数= ，边数= 点数域数=,相关练习,NKOJ 1046NKOJ1052,二分图的最大匹配,相关概念,二分图是这样一种图：图被分成两个顶点集M和N，在同一个集合中的顶点不存在边，只有不在同一集合的顶点之间才存在边，二分图匹配是指求出一组边，其中

11、顶点分别在两个集合中，并且没有两个边有相同的依附顶点，也就是说一个顶点最多只属于一条边。最大匹配就是找出这样的最大边数的一组边。,二分图及其最大匹配示意,二分图最大匹配算法（匈牙利算法）,令g=（x,*,y）是一个二分图，其中x=x1,x2.,y=y1,y2,.令m为g中的任意匹配。 1。将x的所有不与m的边关联的顶点表上￥，并称所有的顶点为未扫描的。转到2。 2。如果在上一步没有新的标记加到x的顶点上，则停，否则 ，转3 3。当存在x被标记但未被扫描的顶点时，选择一个被标记但未被扫描的x的顶点，比如xi，用（xi）标 记y 的所有顶点，这些顶点被不属于m且尚未标记的边连到xi。 现在顶点xi

12、 是被扫描的。如果不存在被标记但未被扫描的顶点，转4。 4。如果在步骤3没有新的标记被标记到y的顶点上，则停，否则转5。 5。当存在y被标记但未被扫描的顶点时。选择y的一个被标记但未被扫描的顶点，比如yj， 用（yj）标记x的顶点，这些顶点被属于m且尚未标记的边连到yj。现在，顶点yj是被扫描的。 如果不存在被标记但未被扫描的顶点则转道2。 由于每一个顶点最多被标记一次且由于每一个顶点最多被扫描一次，本匹配算法在有限步内终止。,相关练习,NKOJ 1060NKOJ 1070,Polya计数原理的相关数学基础,群的概念,(1)群定义 给定集合G和G上的二元运算 ，满足下列条件称为群。(a)封闭性

13、：若a,bG,则存在cG,使得ab=c.(b)结合律成立：任意a,b,cG,有(ab)c=a(bc).(c)有单位元：存在eG,任意aG.ae=ea=a.(d)有逆元：任意aG,存在bG, ab=ba=e. b=a.由于结合律成立，(ab)c=a(bc)可记做abc. 例 证明对于a1,a2,an的乘积，结合律成立. aaa=a (共n个a相乘).,-1,n,群的概念,(2) 简单例子例 G=1,-1在普通乘法下是群。例 G=0,1,2,n-1在mod n的加法下是群.例 二维欧氏空间所有刚体旋转T=Ta构成群。其中Ta = cosa sina -sina cosa TbTa= cosb si

14、nb cosa sina -sinb cosb -sina cosa,群的概念,= cosacosb-sinasinb sinacosb+cosasinb -sinacosb-cosasinb cosacosb-sinasinb= cos(a+b) sin(a+b) =Ta+b -sin(a+b) cos(a+b) 从而有(a)封闭性; (b)结合律成立：(TT)T = T(TT) = TTT ; (c)有单位元： T0 = ; (d)有逆元：Ta =T-a = cosa -sina sina cosa,1 00 1,群的概念,前两例群元素的个数是有限的，所以是有限群；后一例群元素的个数是无限

15、的，所以是无限群。有限群G的元素个数叫做群的阶,记做|G|。若群G的任意二元素a,b恒满足ab=ba。责称G为交换群，或Abel群。设G是群,H是G的子集,若H在G原有的运算之下也是一个群,则称为G的一个子群。,群的概念,基本性质,单位元唯一 e1e2=e2=e1消去律成立 ab=ac b=c, ba=ca b=c每个元的逆元唯一 aa =a a = e, ab = ba = e , aa = ab , a = b(d)(ab.c) =c b a . c b a abc = e,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,群的概念,(e) G有限，aG，则存在最小正整数r

16、，使得a = e.且a = a .证 设|G|=g,则a,a ,a ,a G,由鸽巢原理其中必有相同项。设a =a ,1mlg+1, e=a ,1l-mg，令l-m=r.则有a =a a=e.即a =a .既然有正整数r使得a =e,其中必有最小者，不妨仍设为r. r称为a的阶。易见 H=a,a ,a ,a =e在原有运算下也是一个群。,r,-1,r-1,2,g,g+1,m,l,l-m,r,r-1,r-1,-1,r,2,r-1,r,置换群,置换群是最重要的有限群，所有的有限群都可以用之表示。置换：1,n到自身的1-1变换。n阶置换。1,n目标集。( ), a1a2an是1,n中元的一个排列。n

17、阶置换共有n!个，同一置换用这样的表示可有n!个表示法。例如 p1=( )=( )，n阶置换又可看作1,n上的一元运算，一元函数。,1 2 na1 a2 an,1 2 3 43 1 2 4,3 1 4 22 3 4 1,置换群,置换乘法 P1=( ),P2=( )P1P2=( )( )=( ) 注意：既然先做P1的置换，再做P2的置换就规定了若作为运算符或函数符应是后置的。这与一般习惯的前置不一样。一般而言，对1,n上的n阶置换，i1,n要写成(i)P1P2，而不是P1P2(i). (i)P有时写成i 在上面例中，132,214,323,441.也可写(1)P1P2=2,(2)P1P2=4,(

18、3)P1P2=3,(4)P1P2=1. P2P1=( )( )=( )P1P2.,1 2 3 43 1 2 4,1 2 3 43 1 2 4,1 2 3 44 3 2 1,3 1 2 42 4 3 1,1 2 3 42 4 3 1,P1,P1,P2,P1,P1,P2,P2,P2,1 2 3 44 3 2 1,4 3 2 14 2 1 3,1 2 3 44 2 3 1,置换群,(1)置换群 1,n上的所有n阶置换在上面的乘法定义下是一个群。 (a)封闭性 ( )( )=( ) (b)可结合性 ( )( )( ) =( )=( )( )( ) (c) 有单位元 e=( ) (d) ( ) =( )

19、,1 2 na1 a2 an,a1 a2 anb1 b2 bn,1 2 nb1 b2 bn,1 2 na1 a2 an,a1 a2 anb1 b2 bn,1 2 na1 a2 an,a1 a2 anb1 b2 bn,1 2 nc1 c2 cn,b1 b2 bnc1 c2 cn,b1 b2 bnc1 c2 cn,1 2 n1 2 n,1 2 na1 a2 an,a1 a2 an1 2 n,-1,置换群,(2)例 等边三角形的运动群。 绕中心转动120，不动， 绕对称轴翻转。 P1=( ),P2=( ),P3=( ),P4=( ), P5=( ),P6=( )。 1,n上的所有置换(共n!个)构成

20、一个群，称为对称群，记做Sn.注意：一般说1,n上的一个置换群，不一定是指Sn.但一定是Sn的某一个子群。,1 2 31 2 3,1 2 32 3 1,1 2 33 1 2,1 2 31 3 2,1 2 33 2 1,1 2 32 1 3,12 3,Polya计数原理,参见清华大学相关学习资料（在公共邮箱中）相关练习： 1135: Let it Bead,组合数学相关练习,1038: Lotto 1046: 正整数划分问题1052: 圆的重叠问题1060: Tian Ji - The Horse Racing 1070: 信与信封问题 1108: Binomial Showdown 1135: Let it Bead,