清华大学：《组合数学》课程教学资源（PPT课件讲稿）第二章 母函数与递推关系

组合数学 第二章母函数与递推关系

第二章 母函数与递推关系 组合数学

§21母函数 递推关系是计数的一个强有力的工具 特别是在做算法分析时是必需的。递推关 系的求解主要是利用母函数。当然母函数 尚有其他用处,但这主要是介绍解递推关 系上的应用。例如 (1+ax)1+a2x)…(1+anx) 1+(an+a2+…+an)x+(aa2+aa3+…+an-1an)x +…+aa2…anx (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 ++  = + + ++ + + ++ + +  + −

§21母函数 x2项的系数a2+a03+…+an-1m 中所有的项包括n个元素a1,a2,n中 取两个组合的全体;同理项系数包含了从 n个元素a,,…n中取个元素组合的 全体。以此类推

§2.1 母函数 项的系数 中所有的项包括n个元素a1，a2，…an中 取两个组合的全体；同理项系数包含了从 n个元素a1，a2，… an中取3个元素组合的 全体。以此类推。 2 x a1a2 + a1a3++ an − 1an

§21母函数 若令a1=a2=….=mn-1,在(2-1-1)式 中项系数:a2+a1a3+中每m个组合 有1个贡献,其他各项以此类推。故有 (1+x)y=1+C(n)x+C(n,2)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)2=(1+x) [C(n10)+C(n,1)x+…+C(n2,n)x"] [C(m,0)+C(m,1)x+…+C(m2m)x] x"[C(m+n10)+C(m+n,1)x +…+C(m+n,m+n)x m+n

§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(,r-1)+…+C(m,r)C(n20)

§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+n2m)=C(n,0)C(m,0)+C(n,0)C(m,0) +C(n,0)C(m0) (2-1-3) 正法如下 (1+x)”(1+1/x)=x"(1+x)

§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(n20)+C(n,)x+…+C(n,n)x C(m,0)+C(m,1)x-+…+C(m,m)x-"] =x"[C(m+n,0)+C(m+n,1)x+C(m+n,2)x2 +…+C(m+n,m+n)x m+n 比较等式两端的常数项,即得公式(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(m1)x+C(m2)x2 +C(mn,n)x” 令x=1可得 C(n0)+C(n,l)+C(n,2)+…+C(n,m)=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 =

521母函数 (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)+2C(n,2)+3C(n,3)+…+nC(n,nm) n2 (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