§21母函数 用类似的方法还可以得到: C(n,1)x+2C(n,2)x2+3C(n,3)x +.+nc(n, n)x=nx(I+rn-1 C(,1)+2C(m,2)+32C(n,3)+…+n2C(n2n) =n(n+1)2”2 (2-1-7)
§2.1 母函数 用类似的方法还可以得到： 1 2 3 ( , ) (1 ) ( ,1) 2 ( ,2) 3 ( ,3) − + + = + + + n n nC n n x nx x C n x C n x C n x ( 1)2 (2 -1-7) ( ,1) 2 ( ,2) 3 ( ,3) ( , ) 2 2 2 2 − = + + + + + n n n C n C n C n n C n n
§21母函数 还可以类似地推出一些等式,但通过上面 一些例子已可见函数在研究序列 C(n,0),C(n,1),…,C(n,n 的 关系时所起的作用。对其他序列也有同样的 结果。现引进母函数概念如下 定义:对于序列ao,a构造一函数 G(x=ao+a,x+a,x+ 称函数G(X)是序列a0,a1,的母函数
定义：对于序列 构造一函数： §2.1 母函数 还可以类似地推出一些等式，但通过上面 一些例子已可见函数 在研究序列 关系时所起的作用。对其他序列也有同样的 结果。现引进母函数概念如下： n (1+ x) C(n,0),C(n,1), ,C(n,n) , , , , a0 a1 a2 ( ) , 2 G x = a0 + a1 x + a2 x + 称函数G(x)是序列a0 ,a1 ,a的母函数 2 ,
§21母函数 例如是序列C(n20),C(,1)…,C( 的母函数。 如若已知序列a0,a1,则对应的母函数G(×) 便可根据定义给出。反之,如若以求得序列的 母函数G(x),则该序列也随之确定。 序列a0,a12可记为。{an
序列 可记为 。 如若已知序列 则对应的母函数G(x) 便可根据定义给出。反之，如若以求得序列的 母函数G(x)，则该序列也随之确定。 §2.1 母函数 例如 n ) x +1( C(n,0),C(n,1), ,C(n,n) , , , , a0 a1 a2 , , , , a0 a1 a2 { }n a
§22递推关系 利用递推关系进行计数这个方法在算法分 析中经常用到,举例说明如下 例一Hano题:这是个组合数学中的 著名问题。N个圆盘依其半径大小,从下 而上套在A柱上,如下图示。每次只允许 取一个移到柱B或C上,而且不允许大盘放 在小盘上方。若要求把柱A上的η个盘移到 C柱上请设计一种方法来,并估计要移动 几个盘次。现在只有A、B、C三根柱子可 用
§2.2 递推关系 利用递推关系进行计数这个方法在算法分 析中经常用到，举例说明如下： 例一.Hanoi问题：这是个组合数学中的 著名问题。N个圆盘依其半径大小，从下 而上套在A柱上，如下图示。每次只允许 取一个移到柱B或C上，而且不允许大盘放 在小盘上方。若要求把柱A上的n个盘移到 C柱上请设计一种方法来，并估计要移动 几个盘次。现在只有A、B、C三根柱子可 用
§22递推关系 Hanoi问题是个典型的问题,第一步要设 计算法,进而估计它的复杂性,集估计工作量。 算法:N=2时 最后把B上的圆盘移到C上 到此转移完毕
§2.2 递推关系 Hanoi问题是个典型的问题，第一步要设 计算法，进而估计它的复杂性，集估计工作量。 算法：N=2时 第一步先把最上面的一个圆盘套在 最后把 第二步把下面的一个圆盘移到 B上的圆盘移到C上 C上B上 到此转移完毕 A B C