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

Presentation on theme: "生成函数求解递归式 何润雨 （171240009） 几乎所有内容在参考资料中都有拓展。."— Presentation transcript:

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

2 什么是“生成函数”

3 —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) ——源自“维基百科”

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

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

6 生成函数的代数运算

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

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

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

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

11 简单序列的生成函数

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

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

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

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

16 生成函数解递归式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33 生成函数解递归式 Catalan numbers
见 3.1

34 谢谢大家！

35 参考资料 https://en.wikipedia.org/wiki/Generating_function
%95%B0%E5%AD%A6_(Spring_2015)/Generating_functions science/6-042j-mathematics-for-computer-science-fall /readings/MIT6_042JF10_chap12.pdf notes.pdf 通解在第三个网址的 Operation的更多应用在第三个网址的12.3 老师推荐书目：《具体数学》