【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )

2023-03-28 18:38:20 浏览数 (1)

文章目录

  • 一、给定级数求生成函数
  • 二、给定生成函数求级数

参考博客 :

  • 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
  • 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
  • 【组合数学】生成函数 ( 移位性质 )
  • 【组合数学】生成函数 ( 求和性质 )
  • 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
  • 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★

数列的 通项公式 就是 级数

一、给定级数求生成函数

求

b_n = 7cdot 3^n

的生成函数 ;

已知数列是

1^n

, 对应的生成函数是

{a_n}

,

a_n = 1^n

;

begin{aligned} A(x) = sum_{n=0}^{infty} x^n = frac{1}{1-x} end{aligned}

先根据 数列 通项表示 , 写出级数之和 :

G(x) = 7 times 3^0x^0 7 times 3^1x^1 7 times 3^2x^2 cdots 7 times 3^nx^n cdots

将常数提取到外部 :

G(x) = 7 ( 3^0x^0 3^1x^1 3^2x^2 cdots 3^nx^n cdots )

写成合式 :

G(x) = 7 sumlimits_{n=0}^infty 3^nx^n

根据生成函数换元性质 : 通过换元 , 将

3x

看做一项 :

G(x) = 7 sumlimits_{n=0}^infty (3x)^n

根据 常用生成函数

A(x) = sumlimits_{n=0}^{infty} x^n = cfrac{1}{1-x}

可以得出 :

sumlimits_{n=0}^infty (3x)^n =cfrac{1}{1-3x}

根据生成函数线性性质 , 乘法性质 :

b_n = alpha a_n

, 则

B(x) = alpha A(x)

可以得出最终的生成函数

G(x) = 7 sumlimits_{n=0}^infty (3x)^n = cfrac{7}{1-3x}

二、给定生成函数求级数

给定序列

{b_n}

的生成函数

G(x) = cfrac{2}{1-3x 2x^2}

, 求

{b_n}

先将 生成函数 转化为 其它 生成函数 之和 ;

G(x) = cfrac{2}{1-3x 2x^2}

将

1-3x 2x^2

分解因式 , 分解为

(1-x)(1-2x)

将其转为 如下形式的和 , 分子

A,B

是待定常数 ;

G(x) = cfrac{2}{1-3x 2x^2} = cfrac{A}{1-x} cfrac{B}{1-2x}

将上述式子同分 , 表达成

A, B

的分式 :

G(x) = cfrac{A}{1-x} cfrac{B}{1-2x} = cfrac{A(1-2x) B(1-x)}{(1-x)(1-2x)}
= cfrac{A-2Ax B- Bx}{(1-x)(1-2x)}
= cfrac{(A B) - (2A B ) x}{(1-x)(1-2x)}
= cfrac{(A B) - (2A B ) x}{1-3x 2x^2}

与

G(x) = cfrac{2}{1-3x 2x^2}

的分子的

x

项 与 常数项 对比 :

x

一次方项是

0

, 即

2A B = 0

常数项是

2

, 即

A B = 2

得到方程组 :

begin{cases} A B = 2 \\ 2A B = 0 end{cases}

解上述方程组 , 得到结果 :

begin{cases} A = -2 \\ B = 4 end{cases}

则生成函数最终分解成了 :

G(x) = cfrac{2}{1-3x 2x^2} = cfrac{-2}{1-x} cfrac{4}{1-2x}

使用线性性质 :

cfrac{-2}{1-x}

对应的级数是 :

sumlimits_{n=0}^infty(-2)x^n

, 数列通项是

c_n=-2

;

使用线性性质 , 换元性质 :

cfrac{4}{1-2x}

对应的级数是 :

sumlimits_{n=0}^infty4(2x)^n=sumlimits_{n=0}^infty4cdot 2^nx^n

, 数列通项是

4cdot 2^n

最终的数列是 :

b_n = -2 4cdot 2^n
博客 函数 数学

0 人点赞