生成函数 学习笔记
有一部分没地方写的组合数学，先写这里。
0. pre - learning
1. 上升/下降幂：
\[n^{\underline{k}} = n \times (n-1) \times \cdots \times (n-k+1) \]称为 \(n\) 的下降幂。
同理：
\[n^{\overline{k}} = n \times (n-1) \times \cdots \times (n+k-1) \]称为 \(n\) 的上升幂。
2. 组合数：
\[\operatorname{C}^m_n = \binom{n}{m} = \dfrac{n!}{m!(n-m)!} \]组合数的几个重要公式：
对称性：
\[\binom{n}{m} = \binom{n}{n-m} \]吸收性：
\[\binom{n}{m} = \dfrac{n}{m}\binom{n-1}{m-1} \]递推：
\[\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m} \]证明：不妨直接拆组合数。
也可以考虑杨辉三角。
上指标求和：
\[\sum_{i=m}^n \binom{i}{m} = \binom{n+1}{m+1} \]证明：
\[\sum_{i=m}^n \binom{i}{m} = \binom{m}{m} +\binom{m+1}{m}+\cdots+\binom{n}{m} \]因为 \(\binom{m}{m} = 1 = \binom{m+1}{m+1}\)，所以可以用上文的递推公式将右式的前两项合并得到 \(\binom{m+1}{m+1}+\binom{m+1}{m} = \binom{m+2}{m+1}\)。
接着，可以将 \(\binom{m+2}{m+1}\) 和 \(\binom{m+2}{m}\) 合并得到 \(\binom{m+3}{m+1}\)。
以此类推即可。
3. （广义）二项式定理：
\[(a+b)^n = \sum_{k=0}^{n}\dbinom{n}{k} a^{n-k}b^{k} \]我们考虑更改组合数的定义。
广义二项式系数：
\[\binom{\alpha}{k} = \dfrac{\alpha^{\underline{k}}}{k!},\alpha \in\color{orange}\mathbb{R}\color{qaq},k\in\color{orange}\mathbb{N} \]广义二项式定理：
\[(a+b)^\alpha = \sum_{k=0}^{\infty}\dbinom{\alpha}{k} a^{\alpha-k}b^{k} \]证明需要求导，不会。
上指标反转：
\[\binom{n}{m} = (-1)^m\binom{m-n-1}{m} \]证明：
考虑 \(n^{\underline{m}} = n(n-1)\cdots (n-m+1) = (-1)^m(-n)(-n+1)\cdots(m-n-1)=(m-n-1)^{\underline{m}}\)。等价于右式。证毕。
4. 多项式定理：
对于 \((x_1+x_2+\cdots+x_t)^n\) 的展开式，\(x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t}\) 项的系数是：
\[\dfrac{n!}{n_1!n_2!\cdots n_t!},\sum n_i = n \]证明：考虑组合意义。
先从 \(n\) 中选择 \(n_1\) 个式子，方案数为 \(\dbinom{n}{n_1}\)。
接着，从 \(n-n_1\) 中选择 \(n_2\) 个式子，方案数为 \(\dbinom{n-n_1}{n_2}\)。
\(\cdots\)
最后，从 \(n-n_1-n_2-\cdots-n_{t-1}\) 中选择 \(n_t\) 个式子，方案数为 \(\dbinom{n-n_1-n_2-\cdots-n_{t-1}}{n_t}\)。
由乘法原理，方案数为 \(\dbinom{n}{n_1}\dbinom{n-n_1}{n_2}\cdots\dbinom{n-n_1-n_2-\cdots-n_{t-1}}{n_t}\)。
能够化简为：\(\dfrac{n!}{n_1!n_2!\cdots n_t!}\)。
证毕。
值得注意的是，这个问题等价于可重集的排列方案数。
1. 幂级数展开
由于广义二项式定理的存在，我们可以对某些式子进行展开。以下是几个例子：
\[\begin{aligned} \dfrac{1}{x-1} &= \sum_{k=0}^{\infty}\binom{-1}{k}(-x)^k \\&= \sum_{k=0}^{\infty}\dfrac{(-1)^kk!}{k!}(-x)^k \\&= \sum_{k=0}^{\infty} x^k \\&= 1+x+x^2+\cdots \end{aligned} \]\[\dfrac{1}{x+1} = 1-x+x^2-x^3+x^4+\cdots \]需要记住另外几个常见展开：
\[e^x=\sum_{n\ge 0} \dfrac{1}{n!}x^n \]\[xe^x=\sum_{n\ge 1}\dfrac{n}{n!}x^n \]\[e^{Cx}=\sum_{n\ge 0} \dfrac{C^n}{n!}x^n \]\[\ln(1-x) = -\sum_{n\ge \color{orange}1}\color{qaq}\dfrac{1}{n}x^n \]\[\dfrac{e^x+e^{-x}}{2}=\sum_{n\ge0}\dfrac{1}{(2n+1)!}x^{2n+1} \]\[\dfrac{e^x-e^{-x}}{2}=\sum_{n\ge0}\dfrac{1}{(2n)!}x^{2n} \]可以使用泰勒公式证明，但是 OI 中没必要。
注：我们不关心是否收敛，因为在生成函数中，重要的是系数而非值。
2.OGF
对于数列 \(A\)，其 OGF 定义为：
\[A(x)=\sum_{i\ge0}A_ix^i \]OFG 与无标号计数有关。
例：BZOJ3028 食物。
首先分别给出每个条件对应的生成函数。
\(0\) 或 \(1\) 个：\(1+x\)。
\(0\) 或 \(1\) 或 \(2\) 个：\(1+x+x^2\)。
\(0\) 或 \(1\) 或 \(2\) 或 \(3\) 个：\(1+x+x^2+x^3\)。
奇数个：\(\dfrac{x}{1-x^2}\)。
偶数个：\(\dfrac{1}{1-x^2}\)。
\(3\) 的倍数：\(\dfrac{1}{1-x^3}\)。
\(4\) 的倍数：\(\dfrac{1}{1-x^4}\)。
我们将这些生成函数的式子相乘，得到：
\[\begin{aligned} f(x)&=\dfrac{x}{(1-x)^4} \\&= x\sum_{k=0}^{\infty} \binom{-4}{k}(-x)^k \\&= x\sum_{k=0}^{\infty}(-1)^k\binom{k+3}{3}(-x)^k \\&= \sum_{k=1}^{\infty}\binom{k+2}{3}x^{k} \end{aligned} \]\([x^n]f(x)\) 就是选 \(n\) 个的答案。
正确性：多项式乘法等价于枚举在每一个对象中选择了多少个。
生成函数可以用来求数列的通项公式。
引入：化简 \(\sum_{i=0}^{\infty}(i+1)x^i\)。
设 \(S=1+2x+3x^2+\cdots\)，则 \(xS=x+2x^2+3x^3+\cdots\)。
相减，得：\((1-x)S=1+x+x^2+x^3+\cdots=\dfrac{1}{1-x}\)。
解方程，得： \(S=\dfrac{1}{(1-x)^2}\)。
例：求 fib 数列的通项公式。
即求出 \(f_0=\color{orange}0\color{black},f_1=1,f_n=f_{n-2}+f_{n-1}\) 的通项公式。
依照上例子，我们设生成函数 \(f(x)=\sum_{i=0}^{\infty}f_ix^i\)。
那么有：
\[\begin{aligned} f(x) &= \sum_{i=0}^{\infty}f_ix^i \\ &= f_0+f_1x+\sum_{i=2}^{\infty} (f_{i-2}+f_{i-1}) x^i \\ &= x+\sum_{i=2}^{\infty} (f_{i-1}x^{n-1}\times x+f_{i-2}x^{n-2}\times x^2) \\ &= x+x\sum_{i=0}^{\infty}f_ix^i+x^2\sum_{i=0}^{\infty}f_ix^i \\ &= x+xf(x)+x^2f(x) \end{aligned} \]所以 \(F=\dfrac{x}{1-x-x^2}\)。（封闭形式）
将这个式子进行因式分解，得到 \(\dfrac{x}{(1-\frac{1+\sqrt{5}}{2}x)(1-\frac{1-\sqrt{5}}{2})x}\)。
考虑到我们能够计算出形如 \(\dfrac{c}{1-kx}\) 的式子的值，因此可以使用待定系数法，将封闭形式变为 \(\dfrac{A}{1-\frac{1+\sqrt{5}}{2}x}+\dfrac{B}{1-\frac{1-\sqrt{5}}{2}x}\)。
于是有：
\[A\times (1-\dfrac{1-\sqrt{5}}{2}x) +B\times (1-\dfrac{1+\sqrt{5}}{2}x) = x \\ A+B-A(\dfrac{1-\sqrt{5}}{2}x)-B(\dfrac{1+\sqrt{5}}{2}x)=x \]由于 \(A+B=0\)，有：
\[-A\dfrac{1-\sqrt{5}}{2}-B\dfrac{1+\sqrt{5}}{2}=1 \\ A=\dfrac{1}{\sqrt{5}},B=-\dfrac{1}{\sqrt{5}} \]所以：
\[F=-\dfrac{1}{\sqrt{5}} \times \dfrac{1}{1-\frac{1-\sqrt{5}}{2}x} + \dfrac{1}{\sqrt{5}}\times \dfrac{1}{1-\frac{1+\sqrt{5}}{2}x} \]按一般方法进行展开，得：
\[f(x)=\sum_{n=0}^{\infty}(\dfrac{1-\sqrt{5}}{2})^nx^n \times (-\dfrac{1}{\sqrt{5}}) + \sum_{n=0}^{\infty}(\dfrac{1+\sqrt{5}}{2})^nx^n \times (\dfrac{1}{\sqrt{5}}) \]由此，我们得到了 fib 数列的通项公式：
\[fib_n=[x^n]f(x)=\dfrac{(\dfrac{1+\sqrt{5}}{2})^n-(\dfrac{1-\sqrt{5}}{2})^n}{\sqrt{5}} \]4.EGF
定义一个数列 \(A\) 的指数型生成函数 EGF 为：
\[f(x)=\sum_{i=0}^{\infty}f_i\dfrac{x^i}{i!} \]EGF 一般与有标号计数有关，考虑其组合意义：
假设我们要从 \(r\) 个数中分别选择 \(x_1,x_2,x_3\) 个排成一排，记答案为 \(a_r\)。由多项式定理，\(a_r=\dfrac{r!}{x_1!x_2!x_3!}\)。
有 \(a_r=\sum_{x_1+x_2+x_3=r}\dfrac{r!}{x_1!x_2!x_3!}\)，而我们在定义 EGF 时就已经预处理好了分母，但是没有处理分子 \(r!\)。
令 \(f(i)=\sum_{i=0}^{\infty}\dfrac{x^i}{i!}\)，有 \(a_r=r!\times [x^r]f(x)\)。也就是在 OGF 的基础上再乘以 \(r!\)。
例：用红蓝绿 \(3\) 种颜色去涂 \(1\times n\) 的棋盘，每格涂一种颜色，求使得被涂成红色和蓝色的方格数均为偶数的的涂色方法数。
不妨设 \(G(x)=(1+\dfrac{x^2}{2!}+\dfrac{x^4}{4!}\cdots)^2(1+\dfrac{x}{1!}+\dfrac{x^2}{2!}+\dfrac{x^3}{3!}+\cdots)\)。
则：
\[\begin{aligned} G(x)&=(\dfrac{e^x+e^{-x}}{2})^2e^x \\ &=\dfrac{e^{3x}+2e^x+e^{-x}}{4} \\ &=\sum_{n=0}^{\infty}\dfrac{1}{4}(3^n+2+(-1)^n)\dfrac{x^n}{n!} \end{aligned} \]故答案为 \(\dfrac{1}{4}(3^n+2+(-1)^n)\)。
标签：infty,函数,dfrac,sum,笔记,生成,cdots,sqrt,binom From： https://www.cnblogs.com/ChthollyNS/p/18339881