生成函数

Useless Algorithms 之一。

内容基本来自 OI-Wiki。

序列 $a$ 的普通生成函数定义为形式幂级数：

$$ F(x)=\sum_{n}a_nx_n $$

$a$ 既可以是有穷序列，也可以是无穷序列。例如：

1. 序列 $a=\langle1,2,3\rangle$ 的生成函数是 $a+2x+3x^2$
2. 序列 $a=\langle1,1,1,\cdots\rangle$ 的生成函数是 $\sum_{n\ge 0}x^n=1+x+x^2+x^3+\cdots$
3. 序列 $a=\langle1,2,4,8,16,\cdots\rangle$ 的生成函数是 $\sum_{n\ge 0}2^nx^n$
4. 序列 $a=\langle1,3,5,7,9,\cdots\rangle$ 的生成函数是 $\sum_{n\ge 0}(2n+1)x^n$

简单来说，如果序列 $a$ 有通项公式，那么它的普通生成函数的系数就是通项公式。

设两个序列 $a,b$ 的生成函数分别是 $F(x),G(x)$。

由

$$ F(x)\pm G(x)=\sum_{n}(a_n\pm b_n)x^n $$

得到 $F(x)\pm G(x)$ 是序列 $\langle a_n\pm b_n\rangle$ 的生成函数

由

$$ F(x)G(x)=\sum_{n}x^n\sum_{i=0}^{n}a_ib_{n-i} $$

我们知道 $F(x)G(x)$ 是 $\langle\sum_{i=0}^{n}a_ib_{n-i}\rangle$ 的生成函数。

运用生成函数时，我们会适时将其化为封闭形式来便于化简。

例如，$\langle 1,1,1,\cdots\rangle$ 的生成函数是

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

我们发现

$$ F(x)x+1=F(x) $$

解这个方程¹，

$$ F(x)=\dfrac{1}{1-x} $$

考虑等比数列 $\langle1,p,p^2,p^3,\cdots\rangle$ 的生成函数 $F(x)=\sum_{n\ge 0}p^nx^n$，有

$$ \begin{aligned} F(x)px+1&=F(x)\\ F(x)&=\dfrac{1}{1-px} \end{aligned} $$

例如，数列 $\langle1,2,3,4,\cdots\rangle$ 的生成函数 $F(x)=\sum_{n\ge 0} (n+1)x^n$，根据导数知识，

$$ (x^n)’=nx^{n-1} $$ 于是有

$$ \begin{aligned} F(x)&=\sum_{n\ge 0}(n+1)x^n\\ &=\sum_{n\ge 1}nx^{n-1}\\ &=\sum_{n\ge 0}(x^n)’\\ &=\left(\dfrac{1}{1-x}\right)’\\ &=\dfrac{1}{(1-x)^2} \end{aligned} $$

重新定义组合数运算：

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

注意 $r$ 的范围是复数域，$r^{\underline{k}}$ 是 $r$ 的下降阶乘幂²。这时，对 $\alpha\in\mathbf{C}$，有

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