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

文章目录

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

参考博客 :

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

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

生成函数求和性质 1 :

b_n = sumlimits_{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

数列中的第

项 , 等于

a_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)

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

第

列相加 :

a_0 a_0 x a_0x^2 cdots a_0x^n = a_0cfrac{1}{1-x}

第

列相加 :

a_1 x a_1x^2 cdots a_1x^n = a_1xcfrac{1}{1-x}

vdots

第

列相加 :

a_nx^n = a_nx^ncfrac{1}{1-x}

最终得到 :

B(x) = a_0cfrac{1}{1-x} a_1xcfrac{1}{1-x} cdots a_nx^ncfrac{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 = sumlimits_{i=n}^{infty}a_i

, 并且

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

收敛 , 则

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

博客函数数学

0 人点赞