【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )

韩曙亮

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

5700

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

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

文章目录

参考博客 :

数列的通项公式就是级数

一、给定级数求生成函数

求

b_n = 7\cdot 3^n

的生成函数 ;

已知数列是

1^n

, 对应的生成函数是

\{a_n\}

,

a_n = 1^n

;

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

先根据数列通项表示 , 写出级数之和 :

G(x) = 7 \times 3^0x^0 + 7 \times 3^1x^1 + 7 \times 3^2x^2 + \cdots + 7 \times 3^nx^n + \cdots

将常数提取到外部 :

G(x) = 7 ( 3^0x^0 + 3^1x^1 + 3^2x^2 + \cdots + 3^nx^n + \cdots )

写成合式 :

G(x) = 7 \sum\limits_{n=0}^\infty 3^nx^n

根据生成函数换元性质 : 通过换元 , 将

3x

看做一项 :

G(x) = 7 \sum\limits_{n=0}^\infty (3x)^n

根据常用生成函数

A(x) = \sum\limits_{n=0}^{\infty} x^n = \cfrac{1}{1-x}

可以得出 :

\sum\limits_{n=0}^\infty (3x)^n =\cfrac{1}{1-3x}

根据生成函数线性性质 , 乘法性质 :

b_n = \alpha a_n

, 则

B(x) = \alpha A(x)

可以得出最终的生成函数

G(x) = 7 \sum\limits_{n=0}^\infty (3x)^n = \cfrac{7}{1-3x}

二、给定生成函数求级数

给定序列

\{b_n\}

的生成函数

G(x) = \cfrac{2}{1-3x + 2x^2}

, 求

\{b_n\}

先将生成函数转化为其它生成函数之和 ;

G(x) = \cfrac{2}{1-3x + 2x^2}

将

1-3x + 2x^2

分解因式 , 分解为

(1-x)(1-2x)

将其转为如下形式的和 , 分子

A,B

是待定常数 ;

G(x) = \cfrac{2}{1-3x + 2x^2} = \cfrac{A}{1-x} + \cfrac{B}{1-2x}

将上述式子同分 , 表达成

A, B

的分式 :

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

\ \ \ \ \ \ \ \ \ \ = \cfrac{A-2Ax + B- Bx}{(1-x)(1-2x)}

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

\ \ \ \ \ \ \ \ \ \ = \cfrac{(A + B) - (2A + B ) x}{1-3x + 2x^2}

与

G(x) = \cfrac{2}{1-3x + 2x^2}

的分子的

x

项与常数项对比 :

x

一次方项是

0

, 即

2A + B = 0

常数项是

2

, 即

A + B = 2

得到方程组 :

\begin{cases} A + B = 2 \\\\ 2A + B = 0 \end{cases}

解上述方程组 , 得到结果 :

\begin{cases} A = -2 \\\\ B = 4 \end{cases}

则生成函数最终分解成了 :

G(x) = \cfrac{2}{1-3x + 2x^2} = \cfrac{-2}{1-x} + \cfrac{4}{1-2x}

使用线性性质 :

\cfrac{-2}{1-x}

对应的级数是 :

\sum\limits_{n=0}^\infty(-2)x^n

, 数列通项是

c_n=-2

;

使用线性性质 , 换元性质 :

\cfrac{4}{1-2x}

对应的级数是 :

\sum\limits_{n=0}^\infty4(2x)^n=\sum\limits_{n=0}^\infty4\cdot 2^nx^n

, 数列通项是

4\cdot 2^n

最终的数列是 :

b_n = -2 + 4\cdot 2^n

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

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

博客

函数

数学

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

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

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

博客

函数

数学

登录后参与评论

0 条评论

热度