《清华大学组合数学2》由会员分享，可在线阅读，更多相关《清华大学组合数学2（40页珍藏版）》请在金锄头文库上搜索。
1、母函数母函数 定义：对于序列定义：对于序列a0,a1,a2,构造一函数：构造一函数： G(x)=a0+a1x+a2x2+, 称函数称函数G(x)是序列是序列a0,a1,a2,的母函数的母函数(生成函数生成函数 generating function)。 一个序列和它的母函数一一对应。给了序列便得知它 的母函数；反之，求得母函数序列也随之而定。 从 。 一个序列和它的母函数一一对应。给了序列便得知它 的母函数；反之，求得母函数序列也随之而定。 从G(x)得到序列得到序列an。关键在于要搭起从序列到母函 数，从母函数到序列这两座桥。 。关键在于要搭起从序列到母函 数，从母函数到序列这两座桥。 g(
2、x)=1+x+x2+x3+x4+. = x1 1 回顾母函数的几种计算方式： 1)-2-(2 1) 1 ( , 1) 1(2)(=+=hnhnh 有理分式的分项表示 分母具有特征意义 ,)()()()(L+=+= 32 321xhxhxhxH ,)()()()L+=+=+ 32 2212- 2 xhxhxxH_ L+ += 3 2 )2(2)3( )1(2)2()1()()21( xhh xhhxhxHx 1)1(2)2(: 2 +=hhx 1)2(2)3(: 3 +=hhx LLLL )+ _ )21)(1( )()( 1 xx x xkhxH k k = = = = = = = 1 12
3、1 1 21 1 k kk x xx )( 数列的递归表达式 F0= 0，F1= 1 ， Fn= Fn - 1+ Fn - 2 x B x A xx x xx x xG 2 51 1 2 51 1) 2 51 1)( 2 51 1 ( 1 )( 2 + + = + = = 定义定义 如果序列满足 n a ,0 2211 =+ knknnn aCaCaCaL()152 , 111100 = kk dadadaL ()252 及是常数，则 称为的k阶常系数线性递推关系，称为 的初始条件，称为的 特征多项式. k CCCL, 21110 , k dddL0 k C()152 n a()252 n a
4、 kk kk CxCxCxxC+= 1 1 1 )(L n a k=2 C1=-1, C2=-1 C(x) = x2-x-1 C(x)=0的解为 2 51 112=)()(nhnh C(x) = x2-3x+2 C(x)=0的解为1和2 1221=)()(nhnh 相减得到 02213=+)()()(nhnhnh 2.5 线性常系数递推关系2.5 线性常系数递推关系 设为的母函数)(xG n a LL+= n n xaxaaxG 10 )( 根据(2-5-1)，有 LL L LL L L 0)( 0)( 0)( 2211 11211 1 02211 =+ =+ =+ + + knknnn n
5、kkkk k kkkk k aCaCaCax aCaCaCax aCaCaCax ,0 2211 =+ knknnn aCaCaCaL()152 将这些式子两边分别相加，得到 ( )( ) ( )0 1 0 2 0 1 =+ + = = xGxC xaxGxCxaxG k k k i k i i i i i L 即( )( ) = = =+ 1 0 1 0 2 21 1 k j jk i i i j j k k xaxCxGxCxCxCL 其中 1 0 =C 0)( 0)( 0)( 2211 11211 1 02211 =+ =+ =+ + + knknnn n kkkk k kkkk k a
6、CaCaCax aCaCaCax aCaCaCax L LL L L 令,多项式P(x)的次数k-1。 特征多项式 ( ) = = = 1 0 1 0 k j jk i i i j j xaxCxP ( ) k kk CxCxxC+= L 1 1 因此， k k k xCxC x Cx+= L 1 1 1 kk kk CxCxCxxC+= 1 1 1 )(L 特征多项式 我们知道C(x)=0在复数域中有 k个根。设 ( ( ) )( () ) ( () )( () ) kkkk axaxaxxC i k i kk i =+ = =+ = L L 21 21 21 则k k k xCxC x C
7、x+= += L 1 1 1 于是 ()( )( )xPxGxCxC k k =+L 1 1 ()( ) = = =+ 1 0 1 0 2 21 1 k j jk i i i j j k k xaxCxGxCxCxCL ( ) k kk CxCxxC+= L 1 1 ( ) ( ) () k k xCxC xP xG + = L 1 1 ( ) () ()() )352( 111 21 21 = i k i kk xaxaxa xP L ( () ) ( () )( () ) i k i kk xaxaxa=111 21 21 L (2-5-3)式是有理式，且分子的次数低于分母的次数， 有分项
8、表示，即： t t k t tk t t t t k k k k x A x A x A x A x A x A x A x A x A xG )()( )()( )()( )( + + + + + + + + + = + + + + + + + + + = 111 111 111 2 21 2 2 2 2 22 2 21 1 1 2 1 12 1 11 2 2 1 1 L L L L ( ) () ()() )352( 111 )( 21 21 = i k i kk xaxaxa xP xG L )452( )1 ( 11 = = t i k j j i ij i x A )(xG n i
9、t i k j ijn n nj Aa i 1 11 + = + = = ij A xn的系数是。是常数。 2.5 线性常系数递推关系 定理： 2.5 线性常系数递推关系 定理：设是有理分式，多项式的P(x) 次数低 于Q(x)的次数。则有分项表示，且表示唯一 )( )( xQ xP )( )( xQ xP 证明：证明：设的次数为n，对n用数学归纳法。 )(xQ n=1时，是常数，命题成立。)(xP 假设对小于n的正整数，命题成立。 下面证明对正整数n命题成立。设是 的重根， )(xQ k 0)( ),()()( 11 =xQxQxxQ k 2.5 线性常系数递推关系2.5 线性常系数递推关系
10、 不妨设与互素，设)(xP )(xQ )()( )( )()( )( xQx xP x A xQ xP kk 1 1 1 + = 0 1 11 = = = + + )(/)( )()()()( QPA xPxPxxAQ )/()()()( = =xxAQxPxP 11 的次数低于。 根据归纳假设，可分项表示。 )(xP)(xQ )()( )( 1 1 xQx xP k )( )( xQ xP 因此，可分项表示。由(2-5-6)式及(2-5-7) 式可知表示是唯一的。 (2-5-6) (2-5-7) 以下分别各种情况讨论具体计算的问题。 （1）特征多项式无重根 设 可简化为 ( )xC ( )(
11、 )( () )( () )()() k xxxxC = =L 21 ()452 ( ) = = + + = k i i i k k x A x A x A x A xG 1 2 2 1 1 1 111 L ()852 )452( )1 ( 11 = = t i k j j i ij i x A )(xG 的系数是 n x = = = = k i n iin Aa 1 ()952 k AAA, 21 L可由线性方程组 =+ =+ =+ =+ =+ =+ k k kk kk kk k dAAA dAAA dAAA 11 22 1 11 12211 021 L LL L L ()1052 解出。
12、( )( ) = = = = k i i i x A xG 1 1 ()852 其中d0,d1dk是an的初始值 2.5 线性常系数递推关系2.5 线性常系数递推关系 的系数矩阵的行列式是Vandermonde 行列式 ()1052 11 2 1 1 21 1 1 1 k k kk k aaa aaa L LL L L ()1152 ( () ) = ji ji aa0 不难看出有唯一解。()1052 =+ =+ =+ =+ =+ =+ k k kk kk kk k dAAA dAAA dAAA 11 22 1 11 12211 021 L LL L L 证用数学归纳法证用数学归纳法 21 2
13、 11 xx D = =Q 12 xx = =, )( 12 = = ji ji xx ）式成立时（当）式成立时（当12= =n 证明范德蒙德证明范德蒙德(Vandermonde)行列式行列式 = 1 11 2 1 1 22 2 2 1 21 ).( 111 jin ji n n nn n n n xx xxx xxx xxx D L MMM L L L )1( 之例“归纳法”之例“归纳法” ，阶范德蒙德行列式成立）对于假设（，阶范德蒙德行列式成立）对于假设（11 n )()()(0 )()()(0 0 1111 1 2 13 2 312 2 2 1133122 11312 xxxxxxxxx xxxxxxxxx xxxxxx D n n n nn nn n n = = L MMMM L L L 提出，就有 因子列展开，并把每列的公按第 提出，就有 因子列展开，并把每列的公按第 ), , 2()(1 1 n ixxi L = = 则得行为止倍，一直进行到第 减去上一行的，从最后一行起，每行那么，对 则得行为止倍，一直进行到
