多项式科技

生成函数

序列 $a$ （有穷无穷均可）的普通生成函数定义为形式幂级数：$\displaystyle F(x)=\sum_na_nx^n$。例如：

1. $a=\lang1,2,3\rang$ 的普通生成函数是 $1+2x+3x^2$
2. $a=\lang1,1,1,\dots\rang$ 的普通生成函数是 $\displaystyle\sum_{n\geq 0}x^n$
3. $a=\lang1,2,4,8,16,\dots\rang$ 的生成函数是 $\displaystyle\sum_{n\geq 0}2^nx^n$
4. $a=\lang1,3,5,7,9\rang$ 的生成函数是 $\displaystyle\sum_{n\geq 0}(2n+1)x^n$

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

基本运算

两个序列 $a,b$ 的生成函数 $F(x),G(x)$，则 $F(x)\pm G(x)$ 是序列 $\lang a_n\pm b_n\rang$ 的生成函数。

乘法运算即卷积，推出 $F(x)G(x)$ 是序列 $\left\lang\displaystyle\sum_{i=0}^na_ib_{n-i}\right\rang$ 的生成函数。

形式幂级数形式 $\to$ 封闭形式

例如 $a=\lang1,1,1,\dots\rang$ 的普通生成函数是 $\displaystyle F(x)=\sum_{n\geq 0}x^n$，可以发现 $F(x)x+1=F(x)$，于是解方程得到 $\displaystyle F(x)=\frac{1}{1-x}$，这就是 $\displaystyle\sum_{n\geq 0}x^n$ 的封闭形式。

又例如等比数列 $\lang1,p,p^2,\dots\rang$ 的生成函数 $F(x)=\displaystyle\sum_{n\geq 0}p^nx^n$，有 $F(x)px+1=F(x)$ 得 $F(x)=\displaystyle\frac{1}{1-px}$.

$a=\lang 1,0,1,0,1,\dots\rang$ 的 $F(x)=\displaystyle\sum_{n\geq 0}x^{2n}=\frac{1}{1-x^2}$

$a=\lang 1,2,3,4,\dots\rang$ 的 $F(x)=\displaystyle\sum_{n\geq 0}(n+1)x^n=\sum_{n\geq 0}(x^n)'=\left(\frac{1}{1-x}\right)'=\frac{1}{(1-x)^2}$

$a_n=\begin{pmatrix}m\\n\end{pmatrix}$ 的 $F(x)=\displaystyle\sum_{n\geq 0}\begin{pmatrix}m\\n\end{pmatrix}x^n=(1+x)^m$

$Fib$ 数列定义为 $a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}$，于是有

应用

1. 在许多不同种类的食物中选出 $n$ 个，计算方案数。每种食物的限制如下：

构造生成函数：

全部乘起来得到答案的生成函数：

于是答案 $=\begin{pmatrix}n+2\\n-1\end{pmatrix}=\begin{pmatrix}n+2\\3\end{pmatrix}$

1. $a_{n+1}+a_n=2^n,a_0=0$，求通项。

$f(x)=\displaystyle\sum_{n=0}^{+\infty}a_nx^n$，原式变为 $x^{-1}(a_{n+1}x^{n+1})+a_nx^n=(2x)^n$，再求和有

于是 $\displaystyle a_n=\frac{1}{3}[2^n-(-1)^n]$.

1. 卡特兰数：一个 $n\times n$ 的方阵从 $(0,0)$ 走到 $(n,n)$，不经过对角线的方案数，记作 $C_n$。

有如下关系：$C_n=\displaystyle\sum_{k=0}^nC_{n-k}C_k$，构造 $f(x)=\displaystyle\sum_{n=0}^{+\infty}C_nx^n$，有