【组合数学】生成函数 ( 线性性质 | 乘积性质 )

韩曙亮

发布于 2023-03-28 18:36:31

2860

发布于 2023-03-28 18:36:31

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

文章目录

参考博客 :

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

一、生成函数线性性质

生成函数线性性质 1 :

b_n = \alpha a_n

, 则

B(x) = \alpha A(x)

数列

a_n

的生成函数是

A(x)

, 数列

b_n

的生成函数是

B(x)

,

如果

b_n

数列是

a_n

数列的

\alpha

倍 , 那么对应的生成函数也存在对应的关系 ;

证明方法 : 将两边展开 , 根据定义代入即可 ;

二、生成函数线性性质2

生成函数线性性质 2 :

c_n = a_n + b_n

, 则

C(x) = A(x) + B(x)

数列

a_n

的生成函数是

A(x)

, 数列

b_n

的生成函数是

B(x)

, 数列

c_n

的生成含税是

C(x)

,

数列和的生成函数 , 等于生成函数的和 ;

一个数列是其它数列的线性组合 , 那么将其生成函数进行相应的组合 , 也能求出大的数列的生成函数 ;

证明方法 : 将两边展开 , 根据定义代入即可 ;

三、生成函数乘积性质

生成函数乘积性质 :

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

, 则有

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

数列

a_n

的生成函数是

A(x)

, 数列

b_n

的生成函数是

B(x)

, 数列

c_n

的生成含税是

C(x)

,

数列

a_n

的生成函数 :

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

数列

b_n

的生成函数 :

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

数列

c_n

的生成函数 :

C(x) = c_0 + c_1x + c_2x^2 + \cdots

右边的两个生成函数

A(x)

和

B(x)

相乘 :

(a_0 + a_1x + a_2x^2 + \cdots) \times ( b_0 + b_1x + b_2x^2 + \cdots )

按照多项式乘法 ,

x^0

,

0

次方项 , 即常数项, 构成方法有

1

种 , 两个生成函数中的常数项 , 相乘之后是

a_0 b_0

,

x^1

,

1

次方项 , 构成方法有

2

种 ,

A(x)

中的

a_1x

与

B(x)

中的

b_0

, 构成

x^1

一次方项

a_1b_0x

;

A(x)

中的

a_0

与

B(x)

中的

b_1x

, 构成

x^1

一次方项

a_0b_1x

;

x^1

,

1

次方项的系数是

a_1b_0 + a_0b_1

, 完整的

1

次方项是

(a_1b_0 + a_0b_1)x

x^2

,

2

次方项 , 构成方法有

3

种 ,

A(x)

中的

a_0

与

B(x)

中的

b_2x^2

, 构成

x^2

,

2

次方项

a_0b_2x^2

;

A(x)

中的

a_2x^2

与

B(x)

中的

b_0

, 构成

x^2

,

2

次方项

a_2b_0x^2

;

A(x)

中的

a_1x

与

B(x)

中的

b_1x

, 构成

x^2

,

2

次方项

a_1b_1x^2

;

x^2

,

2

次方项的系数是

a_0b_2 + a_2b_0 + a_1b_1

, 完整的

2

次方项是

(a_0b_2 + a_2b_0 + a_1b_1)x^2

规律 :

x

的

n

次方项 , 其系数是

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

, 由

n+1

项组成 , 每一项的

a_i,b_{n-i}

下标之和是

n

;

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

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

博客

函数

数学

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

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

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

博客

函数

数学

登录后参与评论

0 条评论

热度