下载文档原格式
递推关系与母函数法1.2 递推关系Hanoi塔问题：这是组合数学中的著名问题。
n个圆盘依其半径大小，从下而上套在柱A上，如图1.1所示。
每次只允许取一个转移到柱B或柱C上，而且不允许大盘放在小盘上方。
若要求把柱A上的n个盘转移到柱C上，请设计一种方法，并估计要移动几个盘次，现在只有A，B，C三根柱子可供使用。
设a,b,c是3个塔座。
开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。
各圆盘从小到大编号为1,2,…,n,现要求将塔座a 上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。
在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。
图1.1Hanoi塔是个典型的问题，第一步要设计算法，进而估计它的复杂性，即估计工作量。
这一问题有典型的意义，第一步先解决算法问题，即如何完成n个盘的搬动，进一步还要对算法作出复杂性分析，即对要作多少盘次的搬动进行估计。
算法设计：n=时，第一步先把最上面一个圆盘套在柱B上；第二步把第二个圆盘转2移到柱C上；最后再把柱B上的一个圆盘转移到柱C上，到此转移完毕。
假定1n-个盘子的转移算法已经确定。
对于一般n个圆盘的问题，先把上面的1n-个圆盘转称到柱B上，再把最后一上圆盘转移到柱C上，然后把柱B上的1n-个圆盘转移到柱C上，转移完毕。
上述的算法是递归的连用。
2n=时，第一步便利用n=时已给出了算法；3算法把上面两个圆盘移到柱B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上的两个圆盘转移到柱C上，4,5,,n= 以此类推。
图1.1形象地给出4n=的转移过程。
void hanoi (int n, int a, int b, int c) {if (n > 0) {hanoi (n-1, a, c, b); move (a,b);hanoi (n-1, c, b, a); } }算法分析：令n h 表示n 个圆盘所需要的转移盘次。
第1章 排列与组合1.1 从{1,2,…,50}中找一双数{a,b}，使其满足：()5;() 5.a ab b a b -=-≤[解] (a) 5=-b a将上式分解，得到55a b a b -=+⎧⎨-=-⎩a =b –5，a=1，2，…，45时，b ＝6，7，…，50。
满足a=b-5的点共50-5=45个点. a = b+5，a=5，6，…，50时，b ＝0，1，2，…，45。
满足a=b+5的点共45个点. 所以，共计2×45=90个点. (b) 5≤-b a(610)511(454)1651141531+⨯+⨯-=⨯+⨯=个点。
1.2 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？(c) 两男生A 和B 之间正好有3个女生的排列是多少？[解] (a) 女生在一起当作一个人，先排列，然后将女生重新排列。
（7＋1）!×5!=8!×5!＝40320×120=4838400(b) 先将男生排列有7!种方案，共有8个空隙，将5个女生插入，故需从8个空中选5个空隙，有58C 种选择。
将女生插入，有5!种方案。
故按乘法原理，有：7!×58C ×5!=33868800(种)方案。
(c) 先从5个女生中选3个女生放入A ，B 之间，有35C 种方案，在让3个女生排列，有3!种排列，将这5个人看作一个人，再与其余7个人一块排列，有(7+1)! = 8!由于A ，B 可交换，如图**A***B** 或 **B***A**故按乘法原理，有：2×35C ×3!×8!=4838400（种）1.3 m 个男生，n 个女生，排成一行，其中m ，n 都是正整数，若(a) 男生不相邻(m ≤n+1)； (b) n 个女生形成一个整体； (c) 男生A 和女生B 排在一起； 分别讨论有多少种方案.[解] (a) 先将n 个女生排列，有n!种方法，共有n+1个空隙，选出m 个空隙，共有mn C 1+种方法，再插入男生，有m!种方法，按乘法原理，有：n!×mn C 1+×m!＝n!×)!1(!)!1(m n m n -++×m!=)!1()!1(!m n n n -++种方案。
母函数与求解递推关系组合数学⽤的最多的⼯具要算母函数，究竟什么是母函数呢，先看(1+a1x)(1+a2x)⋯(1+a n x)=1+(a1+a2+⋯a n)x+(a1a2+a1a3+⋯a n−1a n)x2+⋯+a1a2⋯a n x n..x1项系数：a1+a2+⋯a n;x2项系数：a1a2+a1a3+⋯a n−1a n；⋯x n项系数：a1a2⋯a n即x k项系数：a1,a2,⋯,a n取k个组合的全体之和，k=1,2,⋯,n.令a1=a2=⋯=a n=1，即得(1+x)n=1+C(n,1)x+C(n,2)x2+⋯+C(n,n)x n另⼀⽅⾯(1+x)m(1+x)n=(1+x)m+n故$$(1+x)m(1+x)n=C(m,0)+C(m,1)+⋯+C(m,m)x m×C(n,0)+C(n,1)x+⋯+C(n,n)x n=C(m+n,0)+C(m+n,1)+⋯+C(m+n,m+n)x m+n$$⽐较上⾯等式得常系数，C(m,0)C(n,k)+C(m,1)C(n,k−1)+⋯+C(m,k)C(n,0)=C(m+n,k),k=0,1,2,⋯,minm,n这样就证明了这个等式，当然也可⽤组合意义证明。
可见 (1+x)n=1+C(n,1)x+C(n,2)x2+⋯+C(n,n)x n在研究序列C(n,0),C(n,1),⋯,C(n,n)时起作⽤.为此引进母函数得概念.定义对于序列C0,C1,C2⋯构造⼀函数G(x)=C0+C1x+C2X2+⋯称G(x)为序列C0,C1,C2⋯的母函数.例如(1+x)n称为序列C(n,0),C(n,1),⋯,C(n,n)的母函数，序列长度可能是有限的，也可能是⽆限的。
若已知序列可求得母函数，反之若求得母函数，序列也随之确定，因此，序列和对应的母函数是⼀⼀对应的。
现利⽤母函数求递推关系的解，⽤汉诺塔做例⼦.H(n)=2H(n−1)+1,H(1)=1补充定义H0=0，并作如下步骤的形式化演算：x:H1=2H0+1x2:H2=2H1+1x3:H3=2H2+1+⋯G(x)=2x[H0+H1x+H2x2+⋯]+[x+x2+x3+⋯]等式两边分别为H0+H1x+H2x2+⋯=2x∞∑k=0H k x k+∞∑k=1x kx+x2+x3+⋯=x[1+x+x2+⋯]=x 1−x所以得G(x)=2xG(x)+x 1−xG(x)=x(1−x)(1−2x)序列H k的母函数已求得，后⾯是设法从G(x)求序列H k.令Processing math: 100%x(1−x)(1−2x)=A1−2x+B1−x解⽅程得A=1,B=−1所以G(x)=11−2x−11−x=(1+2x+22x2+⋯)−(1+x+x2+⋯)因此H n=2n−1,n=1,2,⋯上⾯利⽤母函数求递推关系的序列，构建序列和母函数有座桥：11−x=1+x+x2+⋯。
