生成函数

普通生成函数

首先对于普通生成函数，对于一个序列 \(a = [a_0, a_1, a_2, \cdots]\) ，其生成函数为 \(f(x) = \sum_{n=0}^{\infty} a_n x^n\) 。当然对于这个无穷级数，其实只有在 \(0 < x < 1\) 时有效，但是实际上这里的 \(x\) 只是一个占位符。

然后对于普通生成函数其加乘都和多项式相同。我们直接上例题：

Fruit

首先我们令生成函数的序列的下标为选择多少个，然后 \(a_i\) 为选择 \(i\) 个时的方案数。

那么单考虑每一个水果，每一个生成函数的序列就是只有在 \([a, b]\) 为 \(1\) 。

然后直接把每一个序列乘在一起，得到的最终序列的第 \(m\) 位就是答案。

实际上就是因为如果乘法计算的是 \(i+j=k\) ，那么相当于就是 \(i,j\) 个水果的方案合并在一起。

当然上面的例子是手动模拟, 也可以采用继续推式子。比如下面这道题：

P10780 BZOJ3028 食物

此时我们把每一部分的生成函数乘在一起，那么相当于生成函数为:

\[ f(x) = \frac{x}{(1-x)^4} \]

我们先想办法构造出 \(\frac{1}{(1-x)^4}\) 。

因为 \(\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n\), 那么我们同时对两边求导：

\[ \frac{1}{(1-x)^2} = \sum_{n=1}^{\infty} nx^{n-1} \]

\[ \frac{2}{(1-x)^3} = \sum_{n=2}^{\infty} n(n-1)x^{n-2} \]

\[ \frac{6}{(1-x)^4} = \sum_{n=3}^{\infty} n(n-1)(x-2)x^{n-3} \]

然后经过简单的变化：

\[ \frac{1}{(1-x)^4} = \sum_{n=0}^{\infty} \frac{n(n+1)(x+2)}6 x^{n} \]

\[ \frac{1}{(1-x)^4} = \sum_{n=0}^{\infty} \binom{n+3}{3} x^{n} \]

\[ \frac{x}{(1-x)^4} = \sum_{n=1}^{\infty} \binom{n+2}{3} x^{n} \]

然后答案就是 \(\binom{m+2}{3}\) 了。

指数型生成函数

其形式为:

\[ f(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!} \]

其余加法乘法照常。

其相对而言的实际意义就相比原来的组合问题，增加了不同排列的贡献。这是因为对于多次乘法：

\[ a_i \frac{x^i}{i!} \cdot a_j \frac{x^j}{j!} \cdots a_k \frac{x^k}{k!} = a_i a_j \cdots a_k \frac{x^{i+j\cdots k}}{i!j!\cdots k!} = a_i a_j \cdots a_k \frac{(i+j\cdots k)!}{i!j!\cdots k!} \frac{x^{i+j\cdots k}}{(i+j\cdots k)!} \]

其中 \(\frac{(i+j\cdots k)!}{i!j!\cdots k!}\) 就是多出来的排列的数量。

化简技巧

有的是否我们需要把 "无穷级数" 和其 "封闭性质" 相互转化这里提供一些展开公式（泰勒展开）：

无穷级数	封闭性质	推导
\(1+x+x^2+x^3\cdots\)	\(\frac{1}{1-x}\)	极限基本知识
\(1+x^2+x^4+x^6\cdots\)	\(\frac{1}{1-x^2}\)	把 \(x\) 替换为 \(x^2\)
\(1+x^3+x^6+x^9\cdots\)	\(\frac{1}{1-x^3}\)	把 \(x\) 替换为 \(x^3\)
\(1+2x+3x^2+4x^3\cdots\)	\(\frac{1}{(1-x)^2}\)	扩展二项式定理
\(1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}\cdots\)	\(e^x\)	不会
\(1-\frac{x}{1!}+\frac{x^2}{2!}-\frac{x^3}{3!}\cdots\)	\(e^{-x}\)	把 \(x\) 替换为 \(-x\)
\(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\frac{x^6}{6!}\cdots\)	\(\frac{e^x + e^{-x}}{2}\)	上面两式相加
\(x+\frac{x^3}{3!}+\frac{x^5}{5!}+\frac{x^7}{7!}\cdots\)	\(\frac{e^x - e^{-x}}{2}\)	上面两式相减

关于扩展二项式定理，其实就是第 \(4\) 个式子的推广：

\[ \frac{1}{(1-x)^k} = \sum_{i=0} \operatorname{C}^i_{k+i-1} x^i \]