北京大学：《离散数学》离散数学之二《代数结构与组合数学》第22章 组合计数方法 22.3 生成函数及其性质 22.4 生成函数的应用

23生成函数及其性质 生成函数的定义 牛顿二项式定理 生成函数的性质 ■生成函数与序列的对应关系

1 22.3 生成函数及其性质 „ 生成函数的定义 „ 牛顿二项式定理 „ 生成函数的性质 „ 生成函数与序列的对应关系

生成函数的定义 设序列{an},构造形式幂级数 G(x)=a0+a1r+ axx+.+arr"+. 称G(x)为{an的生成函数 实例: {C(mm的生成函数为 G(x)=1+C(m,1)x+Cm,2x2+,,=(1+x) 给定正整数k,{}的生成函数为 Gx)=1+kx+kx2+kx3+,,= 1-k

2 设序列{an}，构造形式幂级数 G(x) = a0 + a1x + a2x2 + … + anxn + … 称 G(x)为{an}的生成函数. 实例： {C(m,n)}的生成函数为 G(x)= 1 + C(m,1)x + C(m,2)x2 + … = (1+x)m 给定正整数 k, {kn}的生成函数为 G(x) = 1+ kx + k2x2 + k3x3 + … = 1 − kx 1 生成函数的定义

牛顿二项式定理 牛顿二项式系数: n0 其中r为实数,n为整数 牛顿二项式定理 设为实数,则对一切xy,<1有 +=∑y,其中 a)_a(a-1).a-n+1) nk

3 牛顿二项式系数： ⎪⎪⎩ ⎪⎪⎨⎧ > − − + = < =⎟⎟⎠⎞ ⎜⎜⎝⎛ 0 ! ( 1)...( 1) 1 0 0 0 n n r r r n n n n r 其中 r 为实数，n 为整数 牛顿二项式定理 设α为实数，则对一切 x,y，|x/y|<1 有 ! ( 1)...( 1) ( ) , 0 n n n x y n x y n n n − − + =⎟⎟⎠⎞ ⎜⎜⎝⎛ ⎟⎟⎠⎞ ⎜⎜⎝⎛ + = ∑∞= α α α − α α α α 其中 牛顿二项式定理

牛顿二项式定理(续) (x+y) ∑ n. a-n 其中 a)_a(-1)…、a-n+1) 当a=m时,变成二项式定理 +) ∑ 1+m=∑

4 当 α = m 时，变成二项式定理 ( ) , 0 ∑ ∞ = − ⎟⎟⎠⎞ ⎜⎜⎝⎛ + = n m n m n x y nm x y (1 ) , 0 ∑ ∞ = ⎟⎟⎠⎞ ⎜⎜⎝⎛ + = n m nz nm z ! ( 1)...( 1) ( ) , 0 n n n x y n x y n n n − − + =⎟⎟⎠⎞ ⎜⎜⎝⎛ ⎟⎟⎠⎞ ⎜⎜⎝⎛ + = ∑∞= − α α α α α α α 其中 牛顿二项式定理（续）

二项式定理(续) 当a=m时, a)_(-m)_(-m)-m-1)(-m-n+1) n (-1)m(m+1)…(m+n-1) m+n-1 n! m+n 1+z)-"= ∑(-1 12<1 (1+ 0(m+n ∑ z1 1=1+x+x2+ ∑ (n+1)x

5 | | 1 1 (1 ) 1 (1 ) | | 1 1 ( 1) (1 ) 1 (1 ) 0 0 < ⎟⎟⎠⎞ ⎜⎜⎝⎛ + − = − − = < ⎟⎟⎠⎞ ⎜⎜⎝⎛ + − = − + + = ∑ ∑ ∞ = − ∞ = − z z n m n z z z z n m n z z n n m m n n n m m ∑ ∞ = = + − = = + + + − = 0 2 2 ( 1) (1 ) 1 2, 1 ... 1 1 1, n n n x x m x x x m 当α = -m 时， ⎟⎟⎠⎞ ⎜⎜⎝⎛ + − = − − + + − = − − − − − + =⎟⎟⎠⎞ ⎜⎜⎝⎛ − =⎟⎟⎠⎞ ⎜⎜⎝⎛α n m n n m m m n n m m m n n m n n n 1 ( 1) ! ( 1) ( 1)...( 1) ! ( )( 1）...( 1) 二项式定理（续）

生成函数的性质一线性与乘积 线性性质: 1.b=amn则B(x)=a(x) 2. Cn=anton QI C(x)=A(x)+B(x) 乘积性质: ∑u1bn-;,则C(x)=A(x)B(x) i=0

6 线性性质： 1. bn=αan, 则 B(x)= αA(x) 2. cn=an+bn, 则 C(x)=A(x)+B(x) 乘积性质： 3． , ( ) ( ) ( ) 0 c a b C x A x B x n i n i n i = ∑ = ⋅ = − 则 生成函数的性质—线性与乘积

生成函数的性质一移位 n<l 则B(x)=x1A(x) 0,0,…,0,b,b+1, 非号 1+n 个0 5.b=m+,则B(x) nE 19+

7 4． , ( ) ( ) 0 B x x A x a n l n l b l n l n = ⎩⎨⎧ ≥< = − 则 0, 0, ... , 0, , ..., ,... , , ... , , ... , 1 0 0 1 l l l n l n b b b a a a 14243 + + 个 5．bn=an+l , 则 l l n n n x A x a x B x ∑ − = − = 1 0 ( ) ( ) , , ... , , ... , , , ... 0 1 0 1 1 b b a a a a l l+ 生成函数的性质—移位

生成函数的性质一求和 ∑a,则B(x) A(r) x b b x=mortar x x十a1x+…+anx talx …+anx x x 7.b2=∑a,且4)=∑a收敛,则B以=4(1)-x4() n=0 x

8 6． x A x b a B x n i n i − = ∑ = = 1 ( ) , ( ) 0 则 ... 1 1 ... 1 1 1 1 ( ) ... ... ... 0 1 0 1 1 0 1 0 0 + − + + − + − = = + + + = + = x a x x a x x B x a b x a x a x a x b x a x a x b a n n n n n n n n 7． x A xA x b a A a B x n i i n n i − − = ∑ = ∑ = ∞ = ∞ = 1 (1) ( ) , (1) ( ) 0 且 收敛， 则 生成函数的性质—求和

生成函数性质一换元与微积分 换元性质: 8.b=aam2则B(x)=(ax) 求导与积分性质: 9.b=nm则B(x)=A'(x) 10.bn 0 则B(x)=4(x)dc n+1

9 换元性质： 8．bn=αnan, 则 B(x)=A(αx) 求导与积分性质： 9．bn=nan, 则 B(x)=xA’(x) 10．bn= n + 1 an , 则 = ∫ x A x dx x B x 0 ( ) 1 ( ) 生成函数性质—换元与微积分

生成函数与序列的对应 1.给定序列{an或关于an的递推方程,求生成函数G(x) 利用级数的性质和下述重要级数 ∑(-1)yx 1+xn=0 1+x)2=∑ k=1 2(-12-k+1) k=0 k k 1·35.、2k-3) 2k! (-1)”-(2k-2 +∑ x2=1+∑ 吗1(-1)-(/2k-2 12k2-(k-1)

10 1． 给定序列{an}或关于 an的递推方程, 求生成函数 G(x) 利用级数的性质和下述重要级数 ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∞ = − ∞ − = − − ∞ = − ∞ = ∞ = ∞ = ∞ = ⎟⎟⎠⎞ ⎜⎜⎝⎛ − − − = + ⋅ − − − = + − ⋅ ⋅ − = + − − + = + ⎟⎟⎠⎞ ⎜⎜⎝⎛ + = = − + = − 1 2 1 1 1 1 1 1 1 1 2 1 2 1 2 1 0 2 1 2 1 0 0 1 2 2 2 ( 1) 1 2 ! 2 ( 1)! ( 1) (2 2)! 1 2 ! ( 1) 1 3 5...(2 3) 1 ! ( 1)...( 1) (1 ) 1 ( 1) 1 1 1 1 k k k k k k k k k k k k k k k k k n n n n n x k k k x k k k x k k x k k x k x x x x x 生成函数与序列的对应