资源描述：
《南开大学ACM暑期集训之组合数学.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
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＝＝＝＝＝＝＝＝＝123132312－－－－－－－－－－21323
3、1321STL中生成排列数的函数#includeintA[]={2,3,4,5,6,1};prev_permutation(A,A+6);结果：234516intA[]={2,3,4,5,6,1};next_permutation(A,A+6);结果：234615相关练习NKOJ1038NKOJ1108鸽巢原理鸽巢原理之一鸽巢原理是组合数学中最简单也是最基本的原理，也叫抽屉原理。即“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有两个鸽子。”例１367人中至少有２人的生日相同。例２10双手套中任取11只，其中至少
4、有两只是完整配对的。例３参加一会议的人中至少有２人认识的别的参加者的人数相等。鸽巢原理之二鸽巢原理二m1,m2,…,mn都是正整数，并有m1+m2+…+mn－n+1个鸽子住进n个鸽巢，则至少对某个i有第i个巢中至少有mi个鸽子，i=1,2,…,n．上一小节的鸽巢原理一是这一原理的特殊情况，即m1=m2=…=mn=2，m1+m2+…+mn－n+1=n+1如若不然，则对任一i，都有第i个巢中的鸽子数≤mi－1则鸽巢原理之二鸽子总数≤m1+m2+…+mn－n，与假设相矛盾．推论１m只鸽子进n个巢，至少有一个巢里有「－
5、只鸽子．nm推论２n(m－1
6、)+1只鸽子进n个巢，至少有一个巢内至少有m只鸽子．推论３若m1,m2,…,mn是正整数，且>r－1,则m1,…,mn至少有一个不小于rm1+…+mnn递归关系和生成函数定义：对于序列构造一函数：母函数称函数G(x)是序列的母函数递推关系利用递推关系进行计数这个方法在算法分析中经常用到，举例说明如下：例一.Hanoi问题：这是个组合数学中的著名问题。N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A
7、、B、C三根柱子可用。递推关系Hanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，集估计工作量。算法：N=2时第一步先把最上面的一个圆盘套在B上第二步把下面的一个圆盘移到C上最后把B上的圆盘移到C上到此转移完毕ABC递推关系对于一般n个圆盘的问题，假定n-1个盘子的转移算法已经确定。先把上面的n-1个圆盘经过C转移到B。第二步把A下面一个圆盘移到C上最后再把B上的n-1个圆盘经过A转移到C上ABC递推关系上述算法是递归的运用。n=2时已给
8、出算法；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是算法是对的。以此类推。于是有递推关系算法复杂度为：H(x)是序列的母函数。给定了序列，对应的母函数也确定了。反过来也一样，求得了母函数，对应的序列也就可得而知了。当然，利用递推关系(2-2-1)式
9、也可以依次求得，这样的连锁反应关系，叫做递推关系。递推关系下面介绍如何从(2-2-1)式求得母函数H(x)的一种形式算法。所谓形式算法说的是假定这些幂级数在作四则运算时，一如有限
