【组合数学】生成函数 ( 移位性质 )

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

文章目录

  • 一、生成函数移位性质 1 ( 向后移位 )
  • 二、生成函数移位性质 2 ( 向前移位 )

参考博客 :

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

一、生成函数移位性质 1 ( 向后移位 )

生成函数移位性质 1 ( 向后移位 ) :

b(n) = begin{cases} 0, & n < l \\ a_{n-l}, & n geq l end{cases}

, 则

B(x) = x^l A(x)

由 已知数列

a_n

的 生成函数

A(x)

, 求 另外数列

b_n

的 生成函数

B(x)

;

已知数列

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

, 生成函数为

A(x)

;

数列

b_n

与

a_n

的关系是 ,

b_n

在

a_n

的前面增加了

l

个

0

;

数列

a_n

:

a_0, a_1 , cdots , a_n , cdots

数列

b_n

:

begin{matrix} underbrace{ 0, 0, cdots , 0 } \ l 个 0 end{matrix} ,
a_0, a_1 , cdots , a_n , cdots

数列

b_n

的生成函数 , 前

l

项的系数都是

0

, 所以可以省略 ,

  • 第
l

项 ,

B(x)

的生成函数项是

a_0x^l

, 对应的

A(x)

中的生成函数项是

a_0
  • 第
l 1

项 ,

B(x)

的生成函数项是

a_1x^{l 1}

, 对应的

A(x)

中的生成函数项是

a_1x
B(x)

生成函数 中每项只是在 数列

a_n

的 生成函数

A(x)

每项的基础上 , 乘以

x^l

即可 ;

二、生成函数移位性质 2 ( 向前移位 )

生成函数移位性质 2 ( 向前移位 ) :

b_n = a_{n 1}

, 则

B(x) = cfrac{A(x) - sumlimits_{n=0}^{l-1} a_nx^n }{x^l}

由 已知数列

a_n

的 生成函数

A(x)

, 求 另外数列

b_n

的 生成函数

B(x)

;

已知数列

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

, 生成函数为

A(x)

;

数列

b_n

与

a_n

的关系是 ,

b_n

在

a_n

的基础上向后移动了

l

位 ,

b_0

与

a_l

值相同 ,

b_1

与

a_{l 1}

值相同 ;

,

数列

a_n

:

a_0, a_1 , cdots , a_l , a_{l 1} cdots

数列

b_n

:

b_0 , b_1 , cdots

根据

A(x)

求

B(x)

:

在

A(x)

的基础上 , 减去前

l

项 , 即 从

0

到

l-1

项 ,

a_0 , a_1x , a_2x^2 , cdots a_{l-1}x^{l-1}

, 因此有了

A(x) - sumlimits_{n=0}^{l-1} a_nx^n

;

A(x)

生成函数 的 剩余的项 , 每一项都比

B(x)

多

x^l

倍 , 除以

x^l

即可 ;

在上述

A(x) - sumlimits_{n=0}^{l-1} a_nx^n

基础上 , 除以

x^l

, 得到

B(x) = cfrac{A(x) - sumlimits_{n=0}^{l-1} a_nx^n }{x^l}

;

博客 函数 基础 数学

0 人点赞