【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )

参考博客 :

• 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
• 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
• 【组合数学】生成函数 ( 移位性质 )
• 【组合数学】生成函数 ( 求和性质 )

一、生成函数换元性质

生成函数求和性质 1 :

b n = α n a n b_n = \alpha^n a_n bn​=αnan​ , 则 B ( x ) = A ( α x ) B(x) =A( \alpha x) B(x)=A(αx)

数列 a n a_n an​ 的生成函数是 A ( x ) A(x) A(x) , 数列 b n b_n bn​ 的生成函数是 B ( x ) B(x) B(x) ,

数列 a n = { a 0 , a 1 , a 2 , ⋯   } a_n = \{ a_0 , a_1, a_2 , \cdots \} an​={a0​,a1​,a2​,⋯} , 数列 b n = { α 0 a 0 , α 1 a 1 , α 2 a 2 , ⋯   } b_n = \{ \alpha^0a_0 , \alpha^1a_1, \alpha^2a_2 , \cdots \} bn​={α0a0​,α1a1​,α2a2​,⋯} ;

数列 a n a_n an​ 的生成函数 A ( x ) = a 0 x 0 + a 1 x + a 2 x 2 + ⋯ A(x) = a_0x^0 + a_1x + a_2x^2 + \cdots A(x)=a0​x0+a1​x+a2​x2+⋯

数列 b n b_n bn​ 的生成函数 B ( x ) = α 0 a 0 x 0 + α 1 a 1 x 1 + α 2 a 2 x 2 + ⋯ B(x) = \alpha^0a_0x^0 + \alpha^1a_1x^1 + \alpha^2a_2x^2 + \cdots B(x)=α0a0​x0+α1a1​x1+α2a2​x2+⋯

证明方法 :

在 b n b_n bn​ 的生成函数 B ( x ) B(x) B(x) 中 , 将 α 0 x 0 \alpha^0x^0 α0x0 看作一项 , 将 α 1 x 1 \alpha^1x^1 α1x1 看作一项 , 将 α 2 x 2 \alpha^2x^2 α2x2 看作一项 ,

观察上述项可以看出 , α \alpha α 与 x x x 的幂值是相同的 ,

因此可以 将 α x \alpha x αx 看作一个变量 ,

这样通过换元可以得到 B ( x ) = A ( α x ) B(x) =A( \alpha x) B(x)=A(αx) 公式 ;

二、生成函数求导性质

生成函数求导性质 :

b n = n a n b_n = n a_n bn​=nan​ , 则 B ( x ) = x A ′ ( x ) B(x) =xA'( x) B(x)=xA′(x)

数列 a n a_n an​ 的生成函数是 A ( x ) A(x) A(x) , 数列 b n b_n bn​ 的生成函数是 B ( x ) B(x) B(x) ,

数列 a n = { a 0 , a 1 , a 2 , ⋯   , a n , ⋯   } a_n = \{ a_0 , a_1, a_2 , \cdots , a_n , \cdots \} an​={a0​,a1​,a2​,⋯,an​,⋯} , 数列 b n = { 0 a 0 , a 1 , 2 a 2 , ⋯   , n a n , ⋯   } b_n = \{ 0a_0 , a_1, 2a_2 , \cdots, na_n ,\cdots \} bn​={0a0​,a1​,2a2​,⋯,nan​,⋯} ;

数列 a n a_n an​ 的生成函数 A ( x ) = a 0 x 0 + a 1 x + a 2 x 2 + ⋯ + a n x n + ⋯ A(x) = a_0x^0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots A(x)=a0​x0+a1​x+a2​x2+⋯+an​xn+⋯

数列 b n b_n bn​ 的生成函数 B ( x ) = 0 a 0 x 0 + 1 a 1 x 1 + 2 a 2 x 2 + ⋯ + n a n x n + ⋯ B(x) = 0a_0x^0 + 1a_1x^1 + 2a_2x^2 + \cdots + na_nx^n + \cdots B(x)=0a0​x0+1a1​x1+2a2​x2+⋯+nan​xn+⋯

证明上述性质 :

将 数列 a n a_n an​ 的生成函数 A ( x ) A(x) A(x) 求导 , 再 乘以 x x x , 即可得到 B ( x ) B(x) B(x) ;

A ( x ) = a 0 x 0 + a 1 x + a 2 x 2 + ⋯ + a n x n + ⋯ A(x) = a_0x^0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots A(x)=a0​x0+a1​x+a2​x2+⋯+an​xn+⋯

使用导数公式 : ( x n ) ′ = n x n − 1 (x^n)' = nx^{n-1} (xn)′=nxn−1

参考 : 求导-百度百科

A ′ ( x ) = 0 + a 1 + 2 a 2 x + ⋯ + n a n x n − 1 + ⋯ A'(x) = 0 + a_1 + 2a_2x + \cdots + na_nx^{n-1} + \cdots A′(x)=0+a1​+2a2​x+⋯+nan​xn−1+⋯

x A ′ ( x ) = 0 + a 1 x + 2 a 2 x 2 + ⋯ + n a n x n + ⋯ = B ( x ) xA'(x) = 0 + a_1x + 2a_2x^2 + \cdots + na_nx^{n} + \cdots = B(x) xA′(x)=0+a1​x+2a2​x2+⋯+nan​xn+⋯=B(x)

三、生成函数积分性质

b n = a n n + 1 b_n = \cfrac{a_n}{n+1} bn​=n+1an​​ , 则 B ( x ) = 1 x ∫ 0 x A ( x ) d x B(x) =\cfrac{1}{x} \int^{x}_{0} A( x)dx B(x)=x1​∫0x​A(x)dx

上述性质很难记忆 , 由已知生成函数 , 可以推导出未知的生成函数 , 使用时推导即可 ;