组合数学教学课件.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,在同一个集合中的顶点不存在边,只有不在同一集合的顶点之间才存在边,二分图匹配是指求出一组边,其中
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 组合 数学 教学 课件
限制150内