【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★

文章目录

一、生成函数性质总结
二、生成函数与序列的对应

参考博客 :

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

一、生成函数性质总结

1 . 生成函数线性性质 :

乘法 :

b_n = alpha a_n

, 则

B(x) = alpha A(x)

加法 :

c_n = a_n b_n

, 则

C(x) = A(x) B(x)

2 . 生成函数移位性质 :

向后移位 :

b(n) = begin{cases} 0, & n < l \\ a_{n-l}, & n geq l end{cases}

, 则

B(x) = x^l A(x)

向前移位 :

b_n = a_{n 1}

, 则

B(x) = cfrac{A(x) - sumlimits_{n=0}^{l-1} a_nx^n }{x^l}

3 . 生成函数乘积性质 :

c_n = sumlimits_{i=0}^n a_i b_{n-i}

, 则有

C(x) = A(x) cdot B(x)

生成函数求和性质 :

向前求和 :

b_n = sumlimits_{i=0}^{n}a_i

, 则

B(x) = cfrac{A(x)}{1-x}

向后求和 :

b_n = sumlimits_{i=n}^{infty}a_i

, 并且

A(1) =sumlimits_{i=n}^{infty}a_i

收敛 , 则

B(x) = cfrac{A(1) - xA(x)}{1-x}

4 . 生成函数换元性质 :

b_n = alpha^n a_n

, 则

B(x) =A( alpha x)

5 . 生成函数求导性质 :

b_n = n a_n

, 则

B(x) =xA'( x)

6 . 生成函数积分性质 :

b_n = cfrac{a_n}{n 1}

, 则

B(x) =cfrac{1}{x} int^{x}_{0} A( x)dx

二、生成函数与序列的对应

给定序列

{a_n}

或

a_n

的递推方程 , 求生成函数

G(x)

, 需要使用级数的性质和一些重要的级数 ;

常用的生成函数取值 :

数列相关 :

{a_n}

a_n = 1^n

;

begin{aligned} A(x) & = sum_{n=0}^{infty} x^n = frac{1}{1-x} end{aligned}

{a_n}

a_n = (-1)^n

;

begin{aligned} A(x) & = sum_{n=0}^{infty} (-1)^n x^n = frac{1}{1 x} end{aligned}

{a_n}

a_n = k^n

为正整数 ;

begin{aligned} A(x) & = sum_{n=0}^{infty} k^n x^n = frac{1}{1-kx} end{aligned}

二项式系数相关 :

{a_n}

a_n = dbinom{m}{n}

;

begin{aligned} A(x) & = sum_{n=0}^{infty} dbinom{m}{n} x^n = ( 1 x ) ^m end{aligned}

组合数相关 :

{a_n}

a_n = dbinom{m n-1}{n}

m,n

为正整数 ;

begin{aligned} A(x) & = sum_{n=0}^{infty} dbinom{m n-1}{n} x^n = frac{1}{{(1-x)}^m} end{aligned}

{a_n}

a_n = (-1)^n dbinom{m n-1}{n}

m,n

为正整数 ;

begin{aligned} A(x) & = sum_{n=0}^{infty} (-1)^n dbinom{m n-1}{n} x^n = frac{1}{{(1 x)}^m} end{aligned}

{a_n}

a_n = dbinom{n 1}{n}

为正整数 ;

begin{aligned} A(x) & = sum_{n=0}^{infty} dbinom{n 1}{n} x^n \ & = sum_{n=0}^{infty} (n 1) x^n \ & = frac{1}{{(1-x)}^2} end{aligned}

博客函数数学

0 人点赞