生成函数求解递归式 何润雨 （171240009） 几乎所有内容在参考资料中都有拓展。

什么是“生成函数”

—George Polya, Mathematics and plausible reasoning (1954) A generating function is a device somewhat similar to a bag. Instead of carrying many little objects detachedly, which could be embarrassing, we put them all in a bag, and then we have only one object to carry, the bag. —George Polya, Mathematics and plausible reasoning (1954) Generating function is a clothesline on which we hang up a sequence of numbers for display. —Herbert Wilf, Generatingfunctionology (1994) ——源自“维基百科”

生成函数（Generating Function）是一种形式幂级数，其每一项可以提供关于这个序列的信息。 生成函数可以分为很多种，包括普通生成函数（ordinary generating function , OGF）、指数生成函数、L级数、贝尔级数和狄利克雷级数。 不强调情况下“生成函数”特指普通生成函数 （今天只讲普通生成函数有关）

普通生成函数（OGF） 对于序列 𝑎 0 , 𝑎 1 , 𝑎 2 , … 其普通生成函数为 𝑛=0 ∞ 𝑎 𝑛 𝑥 𝑛 对于序列 𝑎 0 , 𝑎 1 , 𝑎 2 , … 其普通生成函数为 𝑛=0 ∞ 𝑎 𝑛 𝑥 𝑛 这是一个形式幂级数，默认其中x 使得级数收敛

生成函数的代数运算

生成函数的代数运算 对于𝐺 𝑥 = 𝑛≥0 𝑔 𝑛 𝑥 𝑛 Shift : 𝑥 𝑘 𝐺 𝑥 = 𝑛≥𝑘 𝑔 𝑛−𝑘 𝑥 𝑛

生成函数的代数运算 对于𝐺 𝑥 = 𝑛≥0 𝑔 𝑛 𝑥 𝑛 和 𝐹 𝑥 = 𝑛≥0 𝑓 𝑛 𝑥 𝑛 Addition : 𝐹 𝑥 +𝐺 𝑥 = 𝑛≥0 ( 𝑓 𝑛 + 𝑔 𝑛 ) 𝑥 𝑛

生成函数的代数运算 对于𝐺 𝑥 = 𝑛≥0 𝑔 𝑛 𝑥 𝑛 和 𝐹 𝑥 = 𝑛≥0 𝑓 𝑛 𝑥 𝑛 Convolution : 𝐹 𝑥 𝐺 𝑥 = 𝑛≥0 𝑘=0 𝑛 𝑓 𝑘 𝑔 𝑛−𝑘 𝑥 𝑛 乘法的更多应用见参考的第三个的12.3

生成函数的代数运算 对于𝐺 𝑥 = 𝑛≥0 𝑔 𝑛 𝑥 𝑛 Differentiation : 𝐺′ 𝑥 = 𝑛≥0 𝑛+1 𝑔 𝑛+1 𝑥 𝑛

简单序列的生成函数

简单序列的生成函数 对于常数列 1, 1, … 其生成函数为 𝑛=0 ∞ 𝑥 𝑛 = 1 1−𝑥

简单序列的生成函数 对于序列 1, 𝑎, 𝑎 2 , 𝑎 3 , … 其生成函数为 𝑛=0 ∞ (𝑎𝑥) 𝑛 = 1 1−𝑎𝑥

简单序列的生成函数 更特殊的，取 𝑎=−1，其生成函数为 𝑛=0 ∞ (−𝑥) 𝑛 = 1 1+𝑥

简单序列的生成函数 还可以有一些“gaps”，比如对于序列 1, 0, 1, 0, … 其生成函数 为 𝑛=0 ∞ 𝑥 2𝑛 = 1 1− 𝑥 2 奇偶项 注意从右往左

生成函数解递归式

生成函数求解递归式 汉诺塔问题 已知汉诺塔的递推公式 𝐻 𝑛 =2 𝐻 𝑛−1 +1, 𝑛>1 且 𝐻 0 =0, 𝐻 1 =1 其生成函数 𝐺 𝑥 = 𝑛≥0 𝐻 𝑛 𝑥 𝑛

生成函数求解递归式 汉诺塔问题 𝐺 𝑥 = 𝑛≥0 𝐻 𝑛 𝑥 𝑛 ∴𝐺 𝑥 = 𝐻 0 + 2 𝐻 0 +1 𝑥+ …+ 2 𝐻 𝑛−1 +1 𝑥 𝑛 + … ∴𝐺 𝑥 = 𝑛≥1 𝑥 𝑛 +2𝑥 𝑛≥0 𝐻 𝑛 𝑥 𝑛

生成函数求解递归式 汉诺塔问题 ∴𝐺 𝑥 = 𝑛≥1 𝑥 𝑛 +2𝑥 𝑛≥0 𝐻 𝑛 𝑥 𝑛 ∴𝐺 𝑥 = 1 1−𝑥 −1+2𝑥𝐺 𝑥 ∴𝐺 𝑥 = 𝑥 1−𝑥 1−2𝑥

生成函数求解递归式 汉诺塔问题 ∴𝐺 𝑥 = 𝑥 1−𝑥 1−2𝑥 ∴𝐺 𝑥 =− 1 1−𝑥 + 1 1−2𝑥 ∴𝐺 𝑥 =− 𝑛≥0 𝑥 𝑛 + 𝑛≥0 2𝑥 𝑛

生成函数求解递归式 汉诺塔问题 ∴𝐺 𝑥 =− 𝑛≥0 𝑥 𝑛 + 𝑛≥0 2𝑥 𝑛 ∴𝐺 𝑥 = 𝑛≥0 2 𝑛 −1 𝑥 𝑛 ∴ 𝐻 𝑛 = 2 𝑛 −1

生成函数解递归式 【一般步骤】 得到一个递归式 将等式两边进行处理，得出关于𝐺(𝑥)的等式 求出𝐺 𝑥 生成函数解递归式 【一般步骤】 得到一个递归式 将等式两边进行处理，得出关于𝐺(𝑥)的等式 求出𝐺 𝑥 展开𝐺 𝑥 使之成为𝑥的幂级数，比对 𝑥 𝑛 系数得出 𝑎 𝑛 处理时注意G(x) 的形式

生成函数解递归式 Fibonacci numbers 对于递归式 𝐹 𝑛 = 𝐹 𝑛−1 + 𝐹 𝑛−2 (𝑛≥2) 且 𝐹 0 =0, 𝐹 1 =1，其 生成函数为 𝐺 𝑥 = 𝑛≥0 𝐹 𝑛 𝑥 𝑛 =𝑥+ 𝑛≥2 𝐹 𝑛−1 + 𝐹 𝑛−2 𝑥 𝑛 提出前两项，之后每项展开

生成函数解递归式 Fibonacci numbers 不知道大家还记不记得作业四里面的这个题目。

生成函数解递归式 Fibonacci numbers 题目非常循循善诱 非常正常的思路（往下看）

生成函数解递归式 Fibonacci numbers shift 𝐺 𝑥 = 𝑛≥0 𝐹 𝑛 𝑥 𝑛 =𝑥+ 𝑛≥2 𝐹 𝑛−1 + 𝐹 𝑛−2 𝑥 𝑛 𝑥𝐺 𝑥 = 𝑛≥0 𝐹 𝑛 𝑥 𝑛+1 = 𝑛≥1 𝐹 𝑛−1 𝑥 𝑛 = 𝑛≥2 𝐹 𝑛−1 𝑥 𝑛 𝑥 2 𝐺 𝑥 = 𝑛≥0 𝐹 𝑛 𝑥 𝑛+2 = 𝑛≥2 𝐹 𝑛−2 𝑥 𝑛 注意利用F0 = 0

生成函数解递归式 Fibonacci numbers 𝐺 𝑥 =𝑥+ 𝑥+ 𝑥 2 𝐺 𝑥 𝐺 𝑥 = 𝑥 1−𝑥− 𝑥 2 要解出F，先解出G，然后对x的次方的系数进行比较 得出G(x) 之后两种处理方法：泰勒级数（理论可行），暴力分解

生成函数解递归式 Fibonacci numbers 方案一：泰勒级数 𝐺 𝑥 = 𝑥 1−𝑥− 𝑥 2 泰勒：理论可行然而算起来很烦

生成函数解递归式 Fibonacci numbers 方案二：暴力分解

生成函数解递归式 Fibonacci numbers 𝐺 𝑥 = 1 5 1 1−𝜙𝑥 − 1 5 1 1− 𝜙 𝑥 = 1 5 𝑛≥0 𝜙𝑥 𝑛 − 1 5 𝑛≥0 𝜙 𝑥 𝑛 = 𝑛≥0 1 5 ( 𝜙 𝑛 − 𝜙 𝑛 ) 𝑥 𝑛

生成函数解递归式 Fibonacci numbers ∴ 𝐹 𝑛 = 1 5 𝜙 𝑛 − 𝜙 𝑛 = 1 5 1+ 5 2 𝑛 − 1 5 1− 5 2 𝑛 比对xn系数

生成函数解线性递归式（通解） 对于递归式 𝑓 𝑛 = 𝑎 1 𝑓 𝑛−1 + 𝑎 2 𝑓 𝑛−2 + …+ 𝑎 𝑑 𝑓 𝑛−𝑑 + 𝑔 𝑛 (n≥𝑑) 其生成函数为𝐹 𝑥 = ℎ 𝑥 +𝐺 𝑥 1− 𝑎 1 𝑥 − 𝑎 2 𝑥 2 −…− 𝑎 𝑑 𝑥 𝑑 其中𝐺(𝑥)为序列0, 0, …, 0, 𝑔 𝑑 , 𝑔 𝑑+1 , 𝑔 𝑑+2 …（d个0）的生 成函数 其中ℎ 𝑥 = 𝑖=0 𝑑−1 ℎ 𝑖 𝑥 𝑖 , ℎ 𝑖 = 𝑓 0 − 𝑎 1 𝑓 𝑖−1 − …− 𝑎 𝑖 𝑓 0

生成函数解递归式 Catalan numbers 见http://tcs.nju.edu.cn/wiki/index.php/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6_(Spring_2015)/Generating_functions#Solving_the_Catalan_numbers 3.1

谢谢大家！

参考资料 https://en.wikipedia.org/wiki/Generating_function http://tcs.nju.edu.cn/wiki/index.php/%E7%BB%84%E5%90%88%E6 %95%B0%E5%AD%A6_(Spring_2015)/Generating_functions https://ocw.mit.edu/courses/electrical-engineering-and-computer- science/6-042j-mathematics-for-computer-science-fall- 2010/readings/MIT6_042JF10_chap12.pdf http://math.mit.edu/~goemans/18310S15/generating-function- notes.pdf 通解在第三个网址的 12.5.3 Operation的更多应用在第三个网址的12.3 老师推荐书目：《具体数学》