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

韩曙亮

发布于 2023-03-28 18:38:00

1K0

发布于 2023-03-28 18:38:00

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

参考博客 :

一、生成函数性质总结

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) - \sum\limits_{n=0}^{l-1} a_nx^n }{x^l}

3 . 生成函数乘积性质 :

c_n = \sum\limits_{i=0}^n a_i b_{n-i}

, 则有

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

生成函数求和性质 :

向前求和 :

b_n = \sum\limits_{i=0}^{n}a_i

, 则

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

向后求和 :

b_n = \sum\limits_{i=n}^{\infty}a_i

, 并且

A(1) =\sum\limits_{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)

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

常用的生成函数取值 :

1

数列相关 :

\{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

,

k

为正整数 ;

\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}

,

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}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-28，如有侵权请联系 cloudcommunity@tencent.com 删除

博客

函数

数学

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

博客

函数

数学

登录后参与评论

0 条评论

热度