参考博客 :

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

一、生成函数应用场景

生成函数应用场景 :

• 求解递推方程
• 多重集 $r$ 组合计数
• 不定方程解个数
• 整数拆分

多重集 $r$ 组合计数 , 之前 只能计数特殊情况下的组合数 , 也就是选取数 $r$ 小于多重集每一项的重复度 , 才有 组合数 $N=C(k+r-1,r)$ , 如果 $r$ 大于重复度 , 就需要使用生成函数进行求解 ;

不定方程的解个数 , 之前只能求解 没有约束的情况 , 如果对变量有约束 , 如 $x_1$ 只能在某个区间取值 , 这种情况下 , 就必须使用生成函数进行求解 ;

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

回顾多重集排列组合 :

• 可重复的元素 , 有序的选取 , 对应 多重集的排列 ; $全排列=\frac{n!}{n_1!n_2!\cdots n_k!}$ , 非全排列 $k^r,r\le 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_3{x}^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_3{x}^3+\cdots$

$-5xG(x)=-5a_{0}x-5a_1{x}^2-5a_2{x}^3-\cdots$

$6x^{2}G(x)=+6a_0{x}^2+6a_x^3+\cdots$

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

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

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

上述幂次对齐后 , 出现的等号右侧的第三列 $+a_2{x}^2-5a_1{x}^2+6a_0{x}^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_{1}x-5a_{0}x$ 三项 ; 其中的 $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)=\frac{1-7x}{1-5x+6x^2}$

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

先将分母进行因式分解 , 然后设置两个待定系数 , 通分后 , 根据 $x$ 项系数写出方程组 , 最终解该方程组 , 最终可以得到 :

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

$\frac{5}{1-2x}$ 对应的级数是 : $\sum _{n=0}^{\infty }5(2x{)}^n=5\sum _{n=0}^{\infty }{2}^n{x}^n$

$\frac{4}{1-3x}$ 对应的级数是 : $\sum _{n=0}^{\infty }(-4)(3x{)}^n=-4\sum _{n=0}^{\infty }{3}^n{x}^n$

最终生成函数的级数形式为 : $G(x)=5\sum _{n=0}^{\infty }{2}^n{x}^n-4\sum _{n=0}^{\infty }{3}^n{x}^n$

递推方程的通解 : $a_n=5\cdot 2^n-4\cdot 3^n$

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

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/109329784