组合数学 第二章母函数与递推关系
第二章 母函数与递推关系 组合数学
§21母函数 递推关系是计数的一个强有力的工具, 特别是在做算法分析时是必需的。递推关 系的求解主要是利用母函数。当然母函数 尚有其他用处,但这主要是介绍解递推关 系上的应用。例如 (1+anx)(1+a2x)…(1+anx) 1+(a+a2+…+an)x+(a02+aa3+…+an-1an)x +∴+a1a2cmX (2-1-1)
§2.1 母函数 递推关系是计数的一个强有力的工具， 特别是在做算法分析时是必需的。递推关 系的求解主要是利用母函数。当然母函数 尚有其他用处，但这主要是介绍解递推关 系上的应用。例如 (2 -1-1) 1 ( ) ( ) (1 )(1 ) (1 ) 1 2 2 1 2 1 2 1 3 1 1 2 n n n n n n a a a x a a a x a a a a a a x a x a x a x ++ = + + ++ + + ++ + + + −
521母函数 x2项的系数aa2+a13+…+cn=1n 中所有的项包括n个元素a,a2,Ln中 取两个组合的全体;同理项系数包含了从 n个元素al,a,…n中取3个元素组合的 全体。以此类推
§2.1 母函数 项的系数 中所有的项包括n个元素a1，a2，…an中 取两个组合的全体；同理项系数包含了从 n个元素a1，a2，… an中取3个元素组合的 全体。以此类推。 2 x a1a2 + a1a3++ an − 1an
521母函数 若令41=a2=…=mn=1,在(2-1-1)式 中项系数:aa2+aa3+中每m个组合 有1个贡献,其他各项以此类推。故有 (1+x)=1+C(n,1)x+C(n2)x2+…+C(n,n)x" (2-1-2)
§2.1 母函数 若令a1=a2= …=an=1，在（2-1-1）式 中 项系数： 中每一个组合 有1个贡献，其他各项以此类推。故有： 2 x a1a2 + a1a3++ an − 1an (2 -1- 2) (1 ) 1 ( ,1) ( ,2) ( , ) n 2 n + x = +C n x +C n x ++C n n x
§21母函数 另一方面 1+x)"(1+x)”=(1+x)+ [C(n,0)+C(n,1)x+…+C(n2n)x"] C(m20)+C(m,1)x+…+C(m2m)x] x"[C(m+n10)+C(m+n,1)x +…+C(m+n,m+n)xn+
§2.1 母函数 另一方面： m n m n x x x + (1+ ) (1+ ) = (1+ ) m n m m n C m n m n x x C m n C m n x C m C m x C m m x C n C n x C n n x + − − − + + + + = + + + + + + + + + ( , ) [ ( ,0) ( ,1) [ ( ,0) ( ,1) ( , ) ] [ ( ,0) ( ,1) ( , ) ] 1
§21母函数 比较等号两端项对应系数,可得一等式 C(m+n, r)=C(m,O)C(n, r)+ C(m,1)C(n2r-1)+…+C(m,r)C(nO)
§2.1 母函数 比较等号两端项对应系数，可得一等式 ( ,1) ( , 1) ( , ) ( ,0) ( , ) ( ,0) ( , ) C m C n r C m r C n C m n r C m C n r − + + + = +
§21母函数 同样对于(1+x)"(1+1/x)m,n≥m (设 ),用类似的方法可得等式 C(m+n,m)=C(n,0)C(m,0)+C(n,0)C(m,0) +…+C(n,0)C(m,0) 正法如下: (1+x)(1+1/x) (1+x)+n
§2.1 母函数 同样对于 ， （设 ），用类似的方法可得等式： n m (1+ x) (1+1/ x) n m ( ,0) ( ,0) (2 -1-3) ( , ) ( ,0) ( ,0) ( ,0) ( ,0) C n C m C m n m C n C m C n C m + + + = + n m m m n x x x x − + (1+ ) (1+1/ ) = (1+ ) 正法如下：
§21母函数 C(n,0)+C(n2)x+…+C(n,n)x] x"[C(m+n10)+C(m+n,1)x+C(m+n2)y3 [C(m,0)+C(m,1)x+…+C(m,m)x +…+C(m+n,m+n)x+ 比较等式两端的常数项,即得公式(2-1-3)
§2.1 母函数 比较等式两端的常数项，即得公式(2-1-3) m n m m n C m n m n x x C m n C m n x C m n x C m C m x C m m x C n C n x C n n x + − − − + + + + = + + + + + + + + + + + ( , ) [ ( ,0) ( ,1) ( ,2) [ ( ,0) ( ,1) ( , ) ] [ ( ,0) ( ,1) ( , ) ] 2 1
§21母函数 又如等式 (1+x)=C(n0)+C(n,1)x+C(n,2)x2 +…+C(n,n)x 令x=1可得 C(n,0)+C(m,1)+C(n,2)+…+C(n,n)=2 (2-1-4)
§2.1 母函数 又如等式： n C n n x x C n C n x C n x ( , ) (1 ) ( ,0) ( ,1) ( ,2) 2 + + + = + + 令x=1 可得 (2 -1- 4) ( ,0) ( ,1) ( ,2) ( , ) 2 n C n +C n +C n ++C n n =
§21母函数 (2-1-2)式等号的两端对)求导可得 C(n,1)+2C(n,2)+3C(m,3)+…+nC(n,n) n2 (2-1-5) 等式(2-1-5两端令x=1,得: C(n,1)+2C(m2)+3C(n,3)+…+nC(n,n) (2-1-5)
§2.1 母函数 (2-1-2)式等号的两端对x求导可得： 2 (2 -1-5) ( ,1) 2 ( ,2) 3 ( ,3) ( , ) −1 = + + + + n n C n C n C n nC n n 等式(2-1-5)两端令x=1，得： 2 (2 -1-5) ( ,1) 2 ( ,2) 3 ( ,3) ( , ) −1 = + + + + n n C n C n C n nC n n