生成函数解析生成函数|离散数学

生成函数是一种解决递归关系的方法。
让我们考虑一下实数的序列a0, a1, a2 … . ar。对于给定的在t处包含零值的实数区间, 函数G（t）由以下序列定义：G（t）= a0, a1t + a2 t2 +?+ ar tr + … … … .等式（i）
该函数G（t）被称为序列ar的生成函数。
现在, 对于恒定序列1、1、1、1 … .., 生成函数为
可以表示为
G（t）=（1-t）-1 = 1 + t + t2 + t3 + t4 +?[通过二项式展开]
与等式（i）进行比较, 我们得到
a0 = 1, a1 = 1, a2 = 1, 依此类推。
例如, 常数序列1, 2, 3, 4, 5, ..生成函数为G（t）=, 因为它可以表示为G（t）=（1-t）-2 = 1 + 2t + 3t2 + 4t3 +?+（r + 1）tr
与等式（i）进行比较, 我们得到a0 = 1, a1 = 2, a2 = 3, a3 = 4, 依此类推。
Zr的生成函数（Z≠0且Z为常数）由G（t）= 1 + Zt + Z2 t2 + Z3 t3 +?+ Zr tr G（t）= [假定| Zt | < 1]给出因此, G（t）=生成Zr, Z≠0
同样, 如果a（1）r具有生成函数G1（t）, 而a（2）r具有生成函数G2（t）, 则λ1a（1）r +λ2a（2）r具有生成函数λ1 G1（t）+λ2G2（t）。在这里, λ1和λ2是常数。
应用领域生成函数可用于以下目的-

用于解决递归关系
为了证明一些组合身份
用于寻找序列项的渐近公式

示例：解决递归关系ar + 2-3ar + 1 + 2ar = 0
通过生成具有初始条件a0 = 2和a1 = 3的函数的方法。
解决方案：让我们假设

将等式（i）乘以tr并从r = 0到∞求和

（a2 + a3 t + a4 t2 +?）-3（a1 + a2 t + a3 t2 +?）+2（a0 + a1 t + a2 t2 +?）= 0 [∴G（t）= a0 + a1 t + a2 t2 + ?]
+ 2G（t）= 0 … … … … 公式（ii）
现在, 将a0 = 2和a1 = 3代入方程式（ii）并求解, 我们得到

将t = 1放在等式（iii）的两边以找到A。因此-1 =-A∴A = 1
将t =放在等式（iii）的两边即可找到B。因此= B∴B = 1
【生成函数解析】因此, G（t）= .hence, ar = 1 + 2r。