普通生成函数学习笔记

普通生成函数

序列$a_i$的普通生成函数（Ordinary generating function，OGF）：

$$F(x)=\sum_{i\ge 0}a_ix^i$$

举个例子，等比数列的生成函数为

$$\sum_{i\ge 0}x^i=\frac{1}{1-x}\\ \sum_{i\ge 0}a^ix^i=\frac{1}{1-ax}\\$$

这也是 OGF 的常用封闭形式。

牛顿二项式定理

首先我们定义组合数的计算：

$$\binom{r}{k}=\frac{r^{\underline{k}}}{k!}(r\in \mathbb{C},k\in \mathbb{N})$$

其中$r^{\underline{k}} = r(r-1)(r-2)\cdots(r-k+1)$，$r^{\underline{0}} = 1$。$k!$是阶乘。

这样就可以扩展二项式定义为

$$(1+x)^\alpha=\sum_{k\ge 0}\binom{\alpha}{k}x^{k}$$

卡特兰数的生成函数

考虑卡特兰数的递推式

$$h(i)=\sum_{j=0}^{i-1}h(j)h(i-j-1)$$

第一部分

其生成函数定义为

$$\begin{aligned} C(x)&=\sum_{i\ge 0}h(i)x^i\\ &=1+\sum_{i\ge 1}\sum_{j=0}^{i-1}h(j)x^jh(i-j-1)x^{i-j-1}x\\ &=1+x\sum_{j\ge 0}h(j)x^j\sum_{i\ge 0}h(i)x^{i}\\ &=1+xC^2(x) \end{aligned}$$

那么解方程得到

$$C(x)=\frac{1\pm \sqrt{1-4x}}{2x}=\frac{2}{1\mp\sqrt{1-4x}}$$

因为$\lim_{x \to 0}\frac{2}{1+\sqrt{1-4x}}=\frac{2}{1+\sqrt{1}}=1=h(0)$，所以

$$C(x)=\frac{1-\sqrt{1-4x}}{2x}$$

第二部分

接下来我们将它展开为无穷级数。

$$\begin{aligned} (1-4x)^{\frac{1}{2}}&=\sum_{i\ge 0}\binom{\frac{1}{2}}{i}(-4x)^i\\ &=1+\sum_{i\ge 1}\frac{\left(\frac{1}{2}\right)^{\underline{i}}}{i!}(-4x)^i \end{aligned} \tag{1}$$

化简下降幂的分式：

$$\frac{\left(\frac{1}{2}\right)^{\underline{i}}}{i!}=(-1)^{i-1}\frac{1}{2^i}\frac{(2i-3)!!}{i!} \tag{2}$$

化简双阶乘：

$$(2i-3)!!=\frac{(2i-2)!}{(2i-2)(2i-4)\cdots 2}=\frac{(2i-2)!}{2^{i-1} (i-1)!}$$

于是$(2)$就变为

$$\frac{\left(\frac{1}{2}\right)^{\underline{i}}}{i!}=(-1)^{i-1}\frac{1}{2^{2i-1}}\frac{(2i-2)!}{(i-1)!i!} \tag{3}$$

把$(3)$带回$(1)$得到

$$\begin{aligned} (1-4x)^{\frac{1}{2}} &= 1+\sum_{i\ge 1}\frac{\left(\frac{1}{2}\right)^{\underline{i}}}{i!}(-4x)^i \\ &= 1-\sum_{i\ge 1}2\frac{(2i-2)!}{(i-1)!i!}x^i \end{aligned} \tag{4}$$

把$(4)$带回原式得到

$$\begin{aligned} C(x)&=\sum_{i\ge 1}\frac{(2i-2)!}{(i-1)!i!}x^{i-1}\\ &=\sum_{i\ge 0}\frac{(2i)!}{i!(i+1)!}x^{i}\\ &=\sum_{i\ge 0}\frac{1}{i+1}\binom{2i}{i}x^{i} \end{aligned}$$

例题

食物

生成函数依次写成

$$\frac{1}{1-x^2}(1+x)\frac{1-x^3}{1-x}\frac{x}{1-x^2}\frac{1}{1-x^4}\frac{1-x^4}{1-x}(1+x)\frac{1}{1-x^3}$$

化简得到

$$\frac{x}{(1-x)^4}$$

根据牛顿二项式定理得到

$$\begin{aligned} (1-x)^{-4}&=\sum_{i\ge 0}\binom{-4}{i}(-x)^i\\ &=\sum_{i\ge 0}\binom{4+i-1}{i}x^i \end{aligned}$$

那么带回原式得到

$$\begin{aligned} \frac{x}{(1-x)^4}&=\sum_{i\ge 0}\binom{3+i}{i}x^{i+1}\\ &=\sum_{i\ge 0}\binom{3+i}{3}x^{i+1}\\ &=\sum_{i\ge 1}\binom{2+i}{3}x^i \end{aligned}$$

Sweet

生成函数为

$$\begin{aligned} \prod_{i=1}^n\left(\sum_{j=0}^{m_i}x^j\right) &= \prod_{i=1}^n\frac{1-x^{m_i+1}}{1-x}\\ &=(1-x)^{-n}\prod_{i=1}^n(1-x^{m_i+1})\\ \end{aligned}$$

根据牛顿二项式定理得到

$$(1-x)^{-n}=\sum_{i\ge 0}\binom{n+i-1}{i}x^i$$

我们暴力展开后面的多项式，最多只有$2^n$项。考虑每一项对答案的贡献，发现$c_ix^i$的贡献是

$$c_i\sum_{j=a-i}^{b-i}\binom{n+j-1}{n-1}$$

这样就做完了。