【组合数学】生成函数 ( 求和性质 )

韩曙亮

发布于 2023-03-28 18:37:19

1.3K0

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

文章目录

参考博客 :

一、生成函数求和性质 1 ( 向前求和 )

生成函数求和性质 1 :

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

, 则

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

数列

a_n

的生成函数是

A(x)

, 数列

b_n

的生成函数是

B(x)

,

数列

a_n = \{ a_0 , a_1, a_2 , \cdots \}

, 数列

b_n = \{ b_0 , b_1, b_2 , \cdots \}

;

数列

a_n

的生成函数

A(x) = a_0 + a_1x + a_2x^2 + \cdots

数列

b_n

的生成函数

B(x) = b_0 + b_1x + b_2x^2 + \cdots

b_n

数列中的第

n

项 , 等于

a_n

数列中的前

n

项的和 ;

推导

b_n

数列的项 :

b_0 = a_0

b_1 = a_0 + a_1

b_2 = a_0 + a_1 + a_2

\vdots

b_n = a_0 + a_1 + a_2 + \cdots + a_n

推导生成函数的项 :

B(x)

中的

x^0

项 ( 常数项 ) :

b_0 \ \ \ = a_0

B(x)

中的

x^1

项 ( 常数项 ) :

b_1x \ = (a_0 + a_1)x

B(x)

中的

x^2

项 ( 常数项 ) :

b_2x^2 = (a_0 + a_1 + a_2)x^2

\vdots

B(x)

中的

x^n

项 ( 常数项 ) :

b_nx^n = (a_0 + a_1 + a_2 + \cdots + a_n)x^n

将上述

B(x)

中的各项相加 : 相加的策略是纵向相加 , 如下图所示 :

第

1

列相加 :

a_0 + a_0 x + a_0x^2 + \cdots + a_0x^n = a_0\cfrac{1}{1-x}

第

2

列相加 :

a_1 x + a_1x^2 + \cdots + a_1x^n = a_1x\cfrac{1}{1-x}

\vdots

第

n

列相加 :

a_nx^n = a_nx^n\cfrac{1}{1-x}

最终得到 :

B(x) = a_0\cfrac{1}{1-x} + a_1x\cfrac{1}{1-x} + \cdots + a_nx^n\cfrac{1}{1-x} + \cdots

将其中的

\cfrac{1}{1-x}

提取出来 , 就可以得到 :

B(x) = \cfrac{1}{1-x} ( a_0 + a_1x + + \cdots + a_nx^n + \cdots )

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

二、生成函数求和性质 2 ( 向后求和 )

生成函数求和性质 2 :

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}

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

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

博客

函数

数学