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

2023-03-28 18:36:31 浏览数 (1)

文章目录

  • 一、生成函数线性性质
  • 二、生成函数线性性质2
  • 三、生成函数乘积性质

参考博客 :

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

一、生成函数线性性质

生成函数 线性性质 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 = sumlimits_{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

次方项 , 其系数是

sumlimits_{i=0}^n a_i b_{n-i}

, 由

n 1

项组成 , 每一项的

a_i,b_{n-i}

下标之和是

n

;

博客 函数 数学

0 人点赞