趣谈生成函数 =v=

趣谈生成函数 =v=

今天luyouqi在洛谷随机跳题rand出来一道生成函数板子题,然后我给做了(雾

发现小伙伴们还不会生成函数,于是我试着写这篇生成函数简介。(其实我也不怎么会生成函数这么高级的东西,本篇纯属道听途说,大家看着当故事娱乐一下就好)

食用指南

  • 笔和草算纸是推荐的食用工具

从前有一个无限长的随便一个数列\(a = \{2, 1, 4, 7, 4\}\),有一天,一个大佬说:能不能用一个函数表示这个数列呢?于是大佬把\(a\)的每一项当做一个多项式的系数,得到了多项式函数\(f(x) = 2 + x + 4x^2 + 7x^3 + 4x^4\),用来表示上面那个序列。大佬很开心。

大佬的朋友——蒟蒻感到疑惑:这个函数代入一个\(x\),得到的东西有什么意义啊?

大佬思考了一会,说:也没什么意义。

蒟蒻说:那你研究它有个*儿用?

大佬又思考了一会,找到了它的一种用途。假如数列\(a\)代表一类物品,中\(a_i\)表示这类物品中选\(i\)件物品的方案数——例如\(a = \{1, 1, 1\}\)表示A类物品中可以选0件或1件或2件,但不能选大于2件;又例如无限长数列\(b = \{1, 0, 0, 1, 0, 0, 1, 0, 0, 1...\}\)表示B类物品只能选3的倍数件。这时候,把\(f(x) = 1 + x + x^2\)和\(g(x) = 1 + x^3 + x^6 + x^9 ...\)乘起来,得到另一个函数\(h(x) = 1 + x + x^2 + x^3 + x^4 + ...\)。这个函数有什么意义呢?它的第\(i\)项的系数就是选A、B两种物品共\(i\)件的方案数。

蒟蒻说:这有啥,不就是把两个多项式乘起来么?和\(O(n^2)\)一个个枚举有什么区别?

大佬说:嗯……你可以FFT……

蒟蒻:哦。没有这个函数我也知道可以FFT。

大佬不认为这个“用函数表示数列”的东西很没用,他决定继续研究,还给它取了个名字叫做数列的“生成函数”,表示用这个函数能生成(表示)一个数列。

有一天,大佬告诉蒟蒻他发现了一个规律——\(a = \{1, 1, 1, 1, 1...\}\)的生成函数是\(f(x) = \frac{1}{1 - x}\)

蒟蒻说:老哥,您不会是研究数学研究傻了吧?它的生成函数不是\(1 + x + x^2 + x^3...\)嘛?怎么会等于您这个\(\frac{1}{1 - x}\)呢?

大佬说:对啊!\(1 + x + x^2 + x^3...\)就等于\(\frac{1}{1 - x}\)!

蒟蒻:喂,大连市第七人民医院嘛?

大佬:……在\(x\in (-1, 1)\)的时候。

蒟蒻:你不早说!等等,为什么\(x\in (-1, 1)\)时就相等了?

大佬:等比数列求和公式啊,\(1 + x + x^2 + x^3...\)的前\(n\)项和等于\(\frac{1 - x^n}{1 - x}\),这是个无限长的数列,\(n\)趋近于无穷的时候\(x^n\)趋近于0,这不就相等了嘛!

蒟蒻:啊,对啊!可是好好的一个函数,你凭空给限定了定义域,这还是原来那个函数嘛?

大佬:不是你说的生成函数中的\(x\)没有意义嘛!还有,你看\(1 + x^2 + x^4 + x^6...\)这个函数,它是不是等于\(\frac{1}{1-x^2}\)?

蒟蒻:对,把前一个式子中的\(x\)换成\(x^2\)不就好了嘛!可是\(1 + 2x + 3x^2 + 4x^3...\)这个函数,它等于什么?

大佬:等于\(\frac{1}{(1 - x)^2}\)啊!你看,对等式\(\frac{1}{1 - x} = 1 + x + x^2 + x^3...\)两边分别求导,得到……算了,说了你也不懂,那你把两个\(1 + x + x^2 + x^3...\)乘起来不就好了嘛!

蒟蒻:蛤?我看看……的确诶!

大佬:我还知道\(1 + 3x + 6x^2 + 10x^3 + 15x^4...\)的生成函数是多少呢!是\(\frac{1}{(1-x)^3}\)!推广开来,\(\frac{1}{(1 - x)^k}\)生成的数列是\(\sum_i^\infty C_{i + k - 1}^{k - 1} x^i\)!

蒟蒻:为什么啊?

大佬:你看\(\frac{1}{(1 - x)^k}\)就是\(k\)个\(\frac{1}{1 - x}\)相乘,就是\(k\)个\(1 + x + x^2 + x^3...\)相乘嘛。那么它的第\(i\)项系数就是从\(k\)个\(1 + x + x^2 + x^3...\)中每个选出一项,乘起来恰为\(x^i\)的方案数,就是\(i = x_1 + x_2 + ... + x_k\)的非负整数解的组数,你用组合数学中的所谓“隔板法”求一下,是不是\(C_{i + k - 1}^{k - 1}\)?

蒟蒻:有道理!

大佬:了解了\(\frac{1}{1-x^k}\)和\(\frac{1}{(1-x)^k}\)这两种特殊生成函数,就掌握了一类题的技巧——来做道题吧!Luogu P2000 欢迎你!


大佬:我还会用生成函数求斐波那契数列通项!

蒟蒻:这么牛逼?

大佬:首先啊,你看这个斐波那契数列的生成函数\(f(x) = x + x^2 + 2x^3 + 3x^4 + 5x^5 + 8x^6...\),然后把它乘个\(x\),得\(x\cdot f(x) = x^2 + x^3 + 2x^4 + 3x^5 + 5x^6 + 8x^7...\),用前式减去后式,得到\(f(x) - x \cdot f(x) = x + x ^ 3 + x^4 + 2x^5 + 3x^6 + 5x^7... = x + x^2 \cdot f(x)\),所以\(f(x) = \frac{x}{1 - x - x^2}\)!

蒟蒻:可是这不是我们之前见过的那两种特殊生成函数,你怎么把它还原成数列呢?

大佬:我打算把它变成等比数列求和的形式!这个分母\(1-x-x^2\)是可以因式分解的,分解后就是\((1-\frac{1-\sqrt5}{2}x)(1-\frac{1+\sqrt5}{2}x)\),所以\[\frac{x}{1 - x - x^2} = \frac{x}{(1-\frac{1-\sqrt5}{2}x)(1-\frac{1+\sqrt5}{2}x)}\],看着非常难受,裂项一下,得到\[ \frac{x}{(1-\frac{1-\sqrt5}{2}x)(1-\frac{1+\sqrt5}{2}x)} = -\frac{1}{\sqrt5}\frac{1}{(1-\frac{1-\sqrt5}{2}x)} + \frac{1}{\sqrt5}\frac{1}{(1-\frac{1+\sqrt5}{2}x)}\]这就成了两个等比数列求和公式乘个常数再相加的形式了!把两个等比数列还原成数列,得到\[fib_n = -\frac{1}{\sqrt5}(\frac{1-\sqrt5}{2})^n + \frac{1}{\sqrt5}(\frac{1+\sqrt5}{2})^n\]这就是斐波那契数列通项公式了!

蒟蒻:哇!这么神奇!

大佬:据说这种方法可以应用到各种线性齐次递推中哦~

上一篇:剑指 Offer 65. 不用加减乘除做加法 + 位运算


下一篇:【剑指Offer】不用加减乘除做加法 解题报告(Java)