文章目录
一、生成函数换元性质
二、生成函数求导性质
三、生成函数积分性质
参考博客 :
【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
【组合数学】生成函数 ( 线性性质 | 乘积性质 )
【组合数学】生成函数 ( 移位性质 )
【组合数学】生成函数 ( 求和性质 )
一、生成函数换元性质
生成函数求和性质 1 :
b n = α n a n b_n = \alpha^n a_nb
n
=α
n
a
n
, 则 B ( x ) = A ( α x ) B(x) =A( \alpha x)B(x)=A(αx)
数列 a n a_na
n
的生成函数是 A ( x ) A(x)A(x) , 数列 b n b_nb
n
的生成函数是 B ( x ) B(x)B(x) ,
数列 a n = { a 0 , a 1 , a 2 , ⋯ } a_n = \{ a_0 , a_1, a_2 , \cdots \}a
n
={a
0
,a
1
,a
2
,⋯} , 数列 b n = { α 0 a 0 , α 1 a 1 , α 2 a 2 , ⋯ } b_n = \{ \alpha^0a_0 , \alpha^1a_1, \alpha^2a_2 , \cdots \}b
n
={α
0
a
0
,α
1
a
1
,α
2
a
2
,⋯} ;
数列 a n a_na
n
的生成函数 A ( x ) = a 0 x 0 + a 1 x + a 2 x 2 + ⋯ A(x) = a_0x^0 + a_1x + a_2x^2 + \cdotsA(x)=a
0
x
0
+a
1
x+a
2
x
2
+⋯
数列 b n b_nb
n
的生成函数 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 + \cdotsB(x)=α
0
a
0
x
0
+α
1
a
1
x
1
+α
2
a
2
x
2
+⋯
证明方法 :
在 b n b_nb
n
的生成函数 B ( x ) B(x)B(x) 中 , 将 α 0 x 0 \alpha^0x^0α
0
x
0
看作一项 , 将 α 1 x 1 \alpha^1x^1α
1
x
1
看作一项 , 将 α 2 x 2 \alpha^2x^2α
2
x
2
看作一项 ,
观察上述项可以看出 , α \alphaα 与 x xx 的幂值是相同的 ,
因此可以 将 α 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_nb
n
=na
n
, 则 B ( x ) = x A ′ ( x ) B(x) =xA'( x)B(x)=xA
′
(x)
数列 a n a_na
n
的生成函数是 A ( x ) A(x)A(x) , 数列 b n b_nb
n
的生成函数是 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 \}a
n
={a
0
,a
1
,a
2
,⋯,a
n
,⋯} , 数列 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 \}b
n
={0a
0
,a
1
,2a
2
,⋯,na
n
,⋯} ;
数列 a n a_na
n
的生成函数 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 + \cdotsA(x)=a
0
x
0
+a
1
x+a
2
x
2
+⋯+a
n
x
n
+⋯
数列 b n b_nb
n
的生成函数 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 + \cdotsB(x)=0a
0
x
0
+1a
1
x
1
+2a
2
x
2
+⋯+na
n
x
n
+⋯
证明上述性质 :
将 数列 a n a_na
n
的生成函数 A ( x ) A(x)A(x) 求导 , 再 乘以 x xx , 即可得到 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 + \cdotsA(x)=a
0
x
0
+a
1
x+a
2
x
2
+⋯+a
n
x
n
+⋯
使用导数公式 : ( x n ) ′ = n x n − 1 (x^n)' = nx^{n-1}(x
n
)
′
=nx
n−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} + \cdotsA
′
(x)=0+a
1
+2a
2
x+⋯+na
n
x
n−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+a
1
x+2a
2
x
2
+⋯+na
n
x
n
+⋯=B(x)
三、生成函数积分性质
b n = a n n + 1 b_n = \cfrac{a_n}{n+1}b
n
=
n+1
a
n
, 则 B ( x ) = 1 x ∫ 0 x A ( x ) d x B(x) =\cfrac{1}{x} \int^{x}_{0} A( x)dxB(x)=
x
1
∫
0
x
A(x)dx
上述性质很难记忆 , 由已知生成函数 , 可以推导出未知的生成函数 , 使用时推导即可 ;
