参考博客 :

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

一、生成函数性质总结

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 ) = { 0 , n < l a n − l , n ≥ l b(n) =

向前移位 : $b_n=a_{n+1}$ , 则 $B(x)=\frac{A(x)-\sum _{n=0}^{l-1}{a}_n{x}^n}{x^l}$

3 . 生成函数 乘积性质 : $c_n=\sum _{i=0}^n{a}_i{b}_{n-i}$ , 则有 $C(x)=A(x)\cdot B(x)$

生成函数求和性质 :

向前求和 : $b_n=\sum _{i=0}^n{a}_i$ , 则 $B(x)=\frac{A(x)}{1-x}$

向后求和 : $b_n=\sum _{i=n}^{\infty }{a}_i$ , 并且 $A(1)=\sum _{i=n}^{\infty }{a}_i$ 收敛 , 则 $B(x)=\frac{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)=x{A}^{\prime }(x)$

6 . 生成函数积分性质 : $b_n=\frac{a_n}{n+1}$ , 则 $B(x)=\frac{1}{x}{\int }_0^{x}A(x)dx$

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

给定序列 $\{a_n\}$ 或 $a_n$ 的递推方程 , 求生成函数 $G(x)$ , 需要使用级数的性质 和 一些重要的级数 ;

常用的生成函数取值 :

$1$ 数列相关 :

$\{a_n\}$ , $a_n=1^n$ ; A ( x ) = ∑ n = 0 ∞ x n = 1 1 − x

$\{a_n\}$ , $a_n=(-1{)}^n$ ; A ( x ) = ∑ n = 0 ∞ ( − 1 ) n x n = 1 1 + x

$\{a_n\}$ , $a_n=k^n$ , $k$ 为正整数 ; A ( x ) = ∑ n = 0 ∞ k n x n = 1 1 − k x

二项式系数相关 :

$\{a_n\}$ , $a_n=\left(\genfrac{}{}{0ex}{}{m}{n}\right)$ ; A ( x ) = ∑ n = 0 ∞ ( m n ) x n = ( 1 + x ) m

组合数相关 :

$\{a_n\}$ , $a_n=\left(\genfrac{}{}{0ex}{}{m+n-1}{n}\right)$ , $m,n$ 为正整数 ; A ( x ) = ∑ n = 0 ∞ ( m + n − 1 n ) x n = 1 ( 1 − x ) m

$\{a_n\}$ , $a_n=(-1{)}^n(\genfrac{}{}{0ex}{}{m+n-1}{n})$ , $m,n$ 为正整数 ; A ( x ) = ∑ n = 0 ∞ ( − 1 ) n ( m + n − 1 n ) x n = 1 ( 1 + x ) m

$\{a_n\}$ , $a_n=\left(\genfrac{}{}{0ex}{}{n+1}{n}\right)$ , $n$ 为正整数 ;
A ( x ) = ∑ n = 0 ∞ ( n + 1 n ) x n = ∑ n = 0 ∞ ( n + 1 ) x n = 1 ( 1 − x ) 2

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/109326582