组合数学 第二章母函数与递推关系
第二章 母函数与递推关系 组合数学
§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