生成函数

多项式

我们很熟悉单项式，例如： $2ab$，$x^{4}$，$\frac{a}{2}$，$…$

而多项式由单项式组合而成，例如：$2ab+x^{4}+\frac{a}{2}$，$ax+b$，$…$

多项式表达，例如：$y=4x$，$f(x)=x^{2}+2x+1$，$…$。

现在我们有多项式形式：

$$a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+…$$

函数形式：

$$f(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+…= \sum_{i\geq0}a_{i}x^{i}$$

我们现在使

$$a_{0}=1,a_{1}=1,a_{2}=1,…$$

于是：

$$f(x)=1+x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6}+…$$

不难发现：

$$f(1)=1+1+1+1+…=+\infty$$

那么

$$f(\frac{1}{2})=1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+…=?$$

生成函数

令

$$S=1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+…+\frac{1}{2^{n}}$$

将等式两边同时乘 $\frac{1}{2}$：

$$\frac{1}{2}S=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+…+\frac{1}{2^{n}}+\frac{1}{2^{n+1}}$$

所以

$$\frac{1}{2}S=1-\frac{1}{2^{n+1}}$$

所以

$$S=\frac{1-\frac{1}{2^{n+1}}}{1-\frac{1}{2}}$$ $$f(\frac{1}{2})=\frac{1-\frac{1}{2^{n+1}}}{1-\frac{1}{2}}$$ $$f(\frac{1}{x})=\frac{1}{1-\frac{1}{x}}(1-\frac{1}{x^{n+1}})$$

注意：$x!=1$，分母不能为 $0$。

由于 $…$ 代表这个表达式后面还有无穷个单项式，而当 $n$ 无限大时，$\frac{1}{x^{n+1}}$ 无限趋近于 $0$，所以 $f(\frac{1}{2})=2$，$f(\frac{1}{x})=\frac{1}{1-\frac{1}{x}}$

所以

$$f(x)=\frac{1}{1-x}$$

而 $\frac{1}{1-x}(0 < x < 1)$ 即 $f(x)$ 的生成函数，更确切地说是 $1+x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6}+…(0 < x < 1)$ 的生成函数。

极限思想

首先引入一个例子：证明 $0.\dot{9}=1$

在主观上，我们总感觉两者差了一点点，但是这个结果却是事实。

证明：

设

$$x=0.\dot{9}$$

两边同时乘 $10$：

$$10x=9.\dot{9}$$

两者做差：

$$9x=9$$

解得

$$x=1$$

所以

$$0.\dot{9}=1$$

我们还可以换一种证明：

$$0.\dot{9}=\frac{9}{10}+\frac{9}{100}+\frac{9}{1000}+\frac{9}{10000}+…$$ $$=9\times(\frac{1}{10}+\frac{1}{100}+\frac{1}{1000}+\frac{1}{10000}+…)$$ $$=9\times(f(\frac{1}{10})-1)$$ $$f(\frac{1}{10})=\frac{10}{9}$$ $$9\times(f(\frac{1}{10})-1)=9\times\frac{1}{9}=1$$ $$0.\dot{9}=1$$

系数决定函数

$$\sin(x)=x-\frac{1}{3!}x^{3}+\frac{1}{5!}x^{5}-\frac{1}{7!}x^{7}+…$$

它的系数对应为：

$$a_{0}=0,a_{1}=1,a_{2}=0,a_{3}=-\frac{1}{3!},a_{4}=0,a_{5}=\frac{1}{5!},…$$ $$e^x=1+x+\frac{1}{2!}x^{2}+\frac{1}{3!}x^{3}+\frac{1}{4!}x^{4}+…$$

它的系数对应为：

$$a_{0}=1,a_{1}=1,a_{2}=\frac{1}{2!},a_{3}=\frac{1}{3!},a_{4}=\frac{1}{4!},…$$

我们可以发现不同的系数可以用来表示不同的函数，不同的函数也可以被不同的系数表示（就像坐标系的各种函数都可以被表示）。

生成函数加和

斐波那契数列：

$$f(0)=0$$ $$f(1)=1$$ $$f(n)=f(n-1)+f(n-2)$$

求

$$F(n)=f(0)x^{0}+f(1)x^{1}+f(2)x^{2}+…=?$$

（这里建议根据斐波那契数列推导式独立思考片刻）

此时的多项式系数：

$$a_{0}=0,a_{1}=1,a_{2}=1,a_{3}=2,a_{4}=3,a_{5}=5,…$$ $$F(n)=f(0)x^{0}+f(1)x^{1}+f(2)x^{2}+f(3)x^{3}…$$ $$xF(x)=f(0)x^{1}+f(1)x^{2}+f(2)x^{3}+…$$ $$x^{2}F(x)=f(0)x^{2}+f(1)x^{3}+…$$

不难发现 $x$ 的系数大于 $2$ 的每一项关系满足：（$x$ 指数相同的单项式）：$2$ 式的系数 $+3$ 式的系数 $=1$ 式的系数（例如：$x^2$ 的三式系数关系 $f(2)=f(1)+f(0)$）

所以：

$$F(x)-xF(x)-x^{2}F(x)=F(0)x^{0}-F(0)x^{1}-F(1)x^{1}$$

由于：

$$f(0)=0$$ $$f(1)=1$$

所以：

$$F(x)-xF(x)-x^{2}F(x)=x$$ $$F(x)(1-x-x^{2})=x$$ $$F(x)=\frac{x}{1-x-x^{2}}$$

我们现在已经开始建立函数与数列之间的桥梁了

函数：$F(x)=\frac{1}{1-x-x^{2}}$

数列：$f(n)=f(n-1)+f(n-2)$

卷积

生成函数乘一个数或多项式或单项式或生成函数生成新的生成函数的操作叫卷积。

首先我们先回忆乘法分配律：$(a+b)\times(c+d)=a\times c+a\times d+b\times c+b\times d$

过程描述：前一个括号里的单项式分别乘后一个括号里的单项式形成新的多项式。

同理：我们也用生成函数的每一个单项式乘要乘的每一个单项式，形成新的多项式（生成函数）。

令：

$$F(x)=a_0+a_1x+a_2x^2+a_3x^3+…$$ $$G(x)=b_0+b_1x+b_2x^2+b_3x^3+…$$

那么：$F(x)\times G(x)$ 的 $x^4$ 的系数是多少?

$$F(x)\times G(x)=a_0b_0+(a_0b_1+a_1b_0)x+(a_0b_2+a_1b_1+a_2b_0)x^2+…$$

我们不难发现 $a_ib_jx^{i+j}$，所以找到所有 $i+j=4$ 的情况的系数和即可，即：

$$a_0b_4+a_1b_3+a_2b_2+a_3b_1+a_4b_0$$

可以看到，我们从 $F(x)$ 中获取系数为 $[0,4]$，$G(x)$ 中同样只不过顺序不同，两者分别相乘就像“卷”起来一样。

生成函数前缀和

$$F(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+…$$ $$\frac{1}{1-x}=x^0+x^1+x^2+…$$

（系数全为 $1$）

$$F(x)\times\frac{1}{1-x}=a_0x^0+(a_0+a_1)x^1+(a_0+a_1+a_2)x^2+…$$

我们通过目标次数获取想得到的系数。

生成函数实用

求 $1^2+2^2+3^2+…$

首先我们知道系数全为 $1$ 的生成函数为 $f(x)=\frac{1}{1-x}$

我们让它和原生成函数“卷”一下（即前缀和）：$f(x)\times \frac{1}{1-x}=\frac{1}{(1-x)^2}$，此时的系数：$1,2,3,4,5,6…$

再和原生成函数“卷”一下：$f(x)\times \frac{1}{1-x}=\frac{1}{(1-x)^3}$，此时的系数：$1,3,6,10,15,…$

此时和我们的目标可以看出来关系了：$0+1=1,1+3=4,3+6=9,6+10=16$。

所以我们要加它的错位生成函数（即原函数 $\times x$，指数错位带动系数错位）。

$f(x)+x\times f(x)=\frac{x+1}{(1-x)^3}$，此时的系数：$1,4,9,16,25,…$

但是我们要求的是和，所以要再和原生成函数“卷”一次：$f(x)=\frac{1+x}{(1-x)^4}$

住它的下标是 $0$ 开始的，所以我们要他整体在往后错一位：

$$f(x)=\frac{(1+x)\times x}{(1-x)^4}$$ $$=\frac{x^2}{(1-x)^4}+\frac{x}{(1-x)^4}$$ $$=x^2\times(1-x)^{-4}+x\times(1-x)^{-4}$$

二项式定理

$$(a+b)^n=C^0_na^nb^0+C^1_na^{n-1}b^1+…+C^r_na^{n-r}b^r+…+C^n_na^0b^n$$

可以根据需要的 $r$，找到系数 $C^r_n$，得到结果。

指数为负数时，二项式定理同样适用。

$$f(n)=n^2\times(1-n)^{-4}+n\times(1-n)^{-4}$$ $$f(n)=C^{3}_{n+2}+C^{3}_{n+1}$$ $$(^{n+2}_{3})=C^{3}_{n+2}$$ $$f(n)=(^{n+2}_{3})+(^{n+1}_{3})$$ $$f(n)=\frac{n(n+1)(2n+1)}{6}$$

例题：P1313 NOIP2011 提高组 计算系数

生成函数多样性

$$e^x=1+x+\frac{1}{2!}x^{2}+\frac{1}{3!}x^{3}+\frac{1}{4!}x^{4}+…$$

此时的系数为：$a_0=1,a_1=1,a_2=\frac{1}{2!},a_3=\frac{1}{3!},…$

我们此时的多项式形式为：

$$f(x)=a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+…$$

但是，当我们改成：

$$f_2(x)=a_{0}+a_{1}x+\frac{a_{2}}{2!}x^{2}+\frac{a_{3}}{3!}x^{3}+…$$

此时的系数为：$a_0=1,a_1=1,a_2=1,a_3=1,…$

所以不同的系数形式会导致系数不同，生成函数的形式也更加灵活。

不止系数形式可以变形：

$$f_3(s)=a_1+\frac{a_2}{2^s}+\frac{a_3}{3^s}+…$$

（$Dirichlet$ 级生成函数）

我们可以看到它的 $x$ 变成了指数，并且第一位系数是 $a_1$（原因后面解释），这又是一种新的生成函数。

我们现在让它们分别“卷”一下：

$$F(x)=a_{0}+a_{1}x+\frac{a_{2}}{2!}x^{2}+\frac{a_{3}}{3!}x^{3}+…$$ $$G(x)=b_{0}+b_{1}x+\frac{b_{2}}{2!}x^{2}+\frac{b_{3}}{3!}x^{3}+…$$

现在我们要求：$F(x)\times G(x)$

我们前面那已经讲了“卷积”这个概念，我们现在写几位感受一下：

$$F(x)\times G(x)=a_0b_0+(a_0b_1+a_1b_0)x+……$$

跟原来的生成函数长得很像，但是由于系数不同，我们要注意处理，再求一次 $x^4$：

$$(\frac{a_0b_4}{0!4!}+\frac{a_1b_3}{1!3!}+\frac{a_2b_2}{2!2!}+\frac{a_3b_1}{3!1!}+\frac{a_4b_0}{4!0!})x^4$$

现在我们将形式槟城我们新的形式：

$$(\frac{a_0b_4}{0!4!}\times4!+\frac{a_1b_3}{1!3!}\times4!+\frac{a_2b_2}{2!2!}\times4!+\frac{a_3b_1}{3!1!}\times4!+\frac{a_4b_0}{4!0!}\times4!)\frac{x^4}{4!}$$ $$=((^{4}_{0})a_0b_4+(^{4}_{1})a_1b_3+(^{4}_{2})a_2b_2+(^{4}_{3})a_3b_1+(^{4}_{4})a_4b_0)\frac{x^4}{4!}$$

虽然“卷”的样子不同，但方式相同。

$$F(s)=a_1+\frac{a_2}{2^s}+\frac{a_3}{3^s}+…$$ $$G(s)=b_1+\frac{b_2}{2^s}+\frac{b_3}{3^s}+…$$

不难发现 $F(s)\times G(s)$ 的单项式乘法公式是 $\frac{a_ib_j}{(ij)^s}$

此时不同于 $i+j=n$，变成了 $i\times j=n$。

$$F(s)\times G(s)=a_1b_1+\frac{(a_1b_2+a_2b_1)}{2^s}+\frac{(a_1b_3+a_3b_1)}{3^s}+…$$

现在我们求一下 $\frac{1}{18^s}$

$$18=1\times 18=2\times 9=3\times 6=6\times 3=9\times 2=18\times 1$$

所以：

$$\frac{(a_1b_{18}+a_2b_9+a_3b_6+a_6b_3+a_9b_2+a_{18}b_1)}{18^s}$$ $$F(s)\times G(s)=\sum_{n\geq1}\sum_{d|n}\frac{a_db_{\frac{n}{d}}}{n^s}$$

求 $n$ 的约数个数

设 $d(n)$ 表示 $n$ 的约数的个数。

$$\zeta(s)=1+\frac{1}{2^s}+\frac{1}{3^s}+…$$

即

$$F(s)=a_1+\frac{a_2}{2^s}+\frac{a_3}{3^s}+…$$

系数全部为 $1$ 的形式。

这类运算很神奇：

$$\zeta(2)=1+\frac{1}{2^2}+\frac{1}{3^2}+…=\frac{\pi^2}{6}$$

而：

$$\frac{1}{\zeta(s)}=\mu(1)+\frac{\mu(2)}{2^s}+…$$

即为莫比乌斯反演。

回到我们的标题：

$$\zeta(s)\times\zeta(s)=d(1)+\frac{d(2)}{2^s}+\frac{d(3)}{3^s}+…$$

就像我们上面说的

$$F(s)\times G(s)=\sum_{n\geq1}\sum_{d|n}\frac{a_db_{\frac{n}{d}}}{n^s}$$

只不过，所有的系数都变成了 $1$。

所以它的“卷积”就变成了公约数的个数，例如：

$$\frac{(a_1b_{18}+a_2b_9+a_3b_6+a_6b_3+a_9b_2+a_{18}b_1)}{18^s}$$

它的系数变成了 $6$。

因为“卷”的时候根据的是约数才会被“卷”走，所以当系数为 $1$ 时，系数即为约数个数。

生成函数是“高等数学”很基础的工具，还有很多妙用，一定要学会！