【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )

韩曙亮

发布于 2023-03-28 18:40:02

1.3K0

发布于 2023-03-28 18:40:02

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

文章目录

参考博客 :

一、生成函数应用场景

生成函数应用场景 :

求解递推方程
多重集

r

组合计数

不定方程解个数
整数拆分

多重集

r

组合计数 , 之前只能计数特殊情况下的组合数 , 也就是选取数

r

小于多重集每一项的重复度 , 才有组合数

N= C(k + r - 1, r)

, 如果

r

大于重复度 , 就需要使用生成函数进行求解 ;

不定方程的解个数 , 之前只能求解没有约束的情况 , 如果对变量有约束 , 如

x_1

只能在某个区间取值 , 这种情况下 , 就必须使用生成函数进行求解 ;

整数拆分 , 将一个正数拆分多若干整数之和 , 拆分方案个数 , 也可以通过生成函数进行计算 ;

回顾多重集排列组合 :

可重复的元素 , 有序的选取 , 对应 多重集的排列 ;

全排列 = \cfrac{n!}{n_1! n_2! \cdots n_k!}

, 非全排列

k^r , \ \ r\leq n_i

可重复的元素 , 无序的选取 , 对应 多重集的组合 ;

N= C(k + r - 1, r)

二、使用生成函数求解递推方程

递推方程 :

a_n - 5a_{n-1} + 6a_{n-2} = 0

初值 :

a_0 = 1, a_1 = 2

\{a_n\}

数列为

\{ a_0 , a_1, a_2, a_3 , \cdots , a_n , \cdots\}

a_n

对应的生成函数是

G(x) = a_0 + a_1 x + a_2 x^2 + a_3x^3 + \cdots

根据递推方程 , 同时为了使得后面的项可以约掉 , 使用

-5x

乘以

G(x)

生成函数 , 使用

+6x^2

乘以

G(x)

, 得到如下三个式子 ,

-5x

乘以

G(x)

得到的第一项就是

x

的一次方项 , 将该项对应到

G(x)

中的

x

一次方项下面 ,

+6x^2

乘以

G(x)

得到的第一项就是

x

的二次方项 , 将该项对应到

G(x)

中的

x

二次方项下面 ;

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ G(x) = a_0 + a_1 x + a_2 x^2 + a_3x^3 + \cdots

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -5x \ G(x) = \ \ \ \ -5a_0x - 5a_1x^2 - 5a_2x^3 - \cdots

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 6x^2 \,G(x) = \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + \,6a_0x^2 + 6a_x^3 + \cdots

(1-5x+6x^2)G(x) =a_0 + (a_1 - 5a_0)x

上述横线下的式子是横线上面三个式子相加的结果 ;

观察上述右侧第三列 , 图中红框部分 ;

上述幂次对齐后 , 出现的等号右侧的第三列

+ a_2 x^2 -5a_1x^2 + \,6a_0x^2

, 将其中

x^2

提取出来得到

(a_2 - 5a_1 + 6a_0)x^2

, 正好对应递推方程

a_n - 5a_{n-1} + 6a_{n-2} = 0

,

因此有

a_2 - 5a_1 + 6a_0 = 0

, 进而可以得到

(a_2 - 5a_1 + 6a_0)x^2 = 0

由此可以看出 , 如果三个式子全部相加 , 下图右侧蓝色矩形框内 , 全部都是

0

;

目前右侧只剩下

a_0 + a_1x -5a_0x

三项 ; 其中的

a_0 = 1 , a_1 = -2

是初值 ;

最终等式右侧是 :

1 - 2x - 5x = 1-7x

将上述式子代入到

(1-5x+6x^2)G(x) =a_0 + (a_1 - 5a_0)x

中 , 使用

1 - 2x - 5x = 1-7x

替换等式右侧的式子 , 得到 :

(1-5x+6x^2)G(x) =1-7x

G(x) = \cfrac{1-7x}{1-5x+6x^2}

使用给定生成函数 , 求对应的级数的方法 , 将上述式子展开 , 参考【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 ) 二、给定生成函数求级数方法 ,

先将分母进行因式分解 , 然后设置两个待定系数 , 通分后 , 根据

x

项系数写出方程组 , 最终解该方程组 , 最终可以得到 :

G(x) = \cfrac{1-7x}{1-5x+6x^2} = \cfrac{5}{1-2x} - \cfrac{4}{1-3x}

\cfrac{5}{1-2x}

对应的级数是 :

\sum\limits_{n=0}^\infty 5 (2x)^n = 5\sum\limits_{n=0}^\infty 2^n x^n

\cfrac{4}{1-3x}

对应的级数是 :

\sum\limits_{n=0}^\infty (-4) (3x)^n = -4\sum\limits_{n=0}^\infty 3^n x^n

最终生成函数的级数形式为 :

G(x) = 5\sum\limits_{n=0}^\infty 2^n x^n - 4\sum\limits_{n=0}^\infty 3^n x^n

递推方程的通解 :

a_n = 5 \cdot 2^n - 4 \cdot 3^n

基本思路 : 有原来的递推方程 , 导出关于生成函数的递推方程 ;

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

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

变量

博客

函数

数学

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

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

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

登录后参与评论

0 条评论

热度