形如 $F(x)=\sum_{n=0}^{\infty}a_nx^n$ 的函数， $a_n$ 可以提供关于这个序列的信息，一般用于解决组合计算问题。

洛谷p2000

已知如下约束条件：

• $6\mid a$
• $b\le 9$
• $c\le 5$
• $4\mid d$
• $e\le 7$
• $2\mid f$
• $0\le g\le 1$
• $8\mid h$
• $10\mid i$
• $j\le 3$
• $a+b+c+d+e+f+g+h+i+j=n$
• 所有数非负整数

问满足以上约束的所有情况数。

根据上述条件，可以得到如下生成函数：

• $1+x^6+x^{12}+\cdots=\frac 1{1-x^6}$
• $1+x+x^2+\cdots +x^9=\frac {1-x^{10}}{1-x}$
• $1+x+x^2+\cdots +x^5=\frac {1-x^6}{1-x}$
• $1+x^4+x^8+\cdots=\frac 1{1-x^4}$
• $1+x+x^2+\cdots +x^7=\frac {1-x^8}{1-x}$
• $1+x^2+x^4+\cdots=\frac 1{1-x^2}$
• $1+x=\frac {1-x^2}{1-x}$
• $1+x^8+x^{16}+\cdots=\frac 1{1-x^8}$
• $1+x^{10}+x^{20}+\cdots=\frac 1{1-x^{10}}$
• $1+x+x^2+x^3=\frac {1-x^4}{1-x}$

全部相乘得到 $\frac 1{(1-x)^5}=\sum_{n=0}^{\infty} {n+4 \choose n}x^n=\sum_{n=0}^{\infty} {n+4 \choose 4}x^n$。

于是答案为 ${n+4 \choose 4}$。

已知卡特兰数定义

$$c_n=\begin{cases} 1, & n=0\\ \sum_{i=0}^{n-1}c_ic_{n-i-1}, & n\gt 0 \end{cases}$$

求 $c_n$ 通项公式。

$$ \begin{equation}\begin{split} F(x)&=\sum_{n=0}^{\infty}c_nx^n\\ &=1+\sum_{n=1}^{\infty}c_nx^n\\ &=1+\sum_{n=1}^{\infty}\sum_{i=0}^{n-1}c_ic_{n-i-1}x^n\\ &=1+x\sum_{n=0}^{\infty}\sum_{i=0}^{n-1}c_ic_{n-i}x^n\\ &=1+xF^2(x) \end{split}\end{equation} $$ 解得 $F(x)=\frac {1\pm\sqrt{1-4x}}{2x}$，又有 $F(0)=c_0=1$，于是发现只有 $F(x)=\frac {1-\sqrt{1-4x}}{2x}$ 一种可能。

$$ \begin{equation}\begin{split} \sqrt{1-4x}&=\sum_{n=0}^{\infty}{\frac 12 \choose n}(-4x)^n\\ &=1+\sum_{n=1}^{\infty}\frac{(-1)^{n-1}(2n-3)!!}{2^nn!}(-4x)^n\\ &=1+\sum_{n=1}^{\infty}\frac{(-1)^{n-1}(2n-2)!}{2^n(2n-2)!!n!}(-4x)^n\\ &=1+\sum_{n=1}^{\infty}\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!n!}(-4x)^n\\ &=1-2\sum_{n=1}^{\infty}\frac{(2n-2)!}{(n-1)!n!}x^n\\ &=1-2x\sum_{n=0}^{\infty}\frac{(2n)!}{n!(n+1)!}x^n\\ \end{split}\end{equation} $$ 所以有 $$ \begin{equation}\begin{split} F(x)&=\frac {1-\sqrt{1-4x}}{2x}\\ &=\frac {1-\left(1-2x\sum_{n=0}^{\infty}\frac{(2n)!}{n!(n+1)!}x^n\right)}{2x}\\ &=\sum_{n=0}^{\infty}\frac{(2n)!}{n!(n+1)!}x^n \end{split}\end{equation} $$ 于是有 $c_n=\frac{(2n)!}{n!(n+1)!}=\frac{2n \choose n}{n+1}$。

求满足下列条件的序列数：

1. $a_1+a_2+\cdots +a_k=n$
2. $a_1\ge a_2\ge\cdots \ge a_k\ge 1$

$$\prod_{i=1}^{\infty}1-x^i=1+\sum_{k=1}^{\infty} (-1)^kx^{k(3k\pm 1)/2}=1-x-x^2+x^5+x^7-x^{12}-x^{15}+\cdots$$

先考虑 $a_1\le t$ 的情况。

只选择 $1$ 的方案的生成函数为 $1+x+x^2+\cdots=\frac 1{1-x}$。

只选择 $2$ 的方案的生成函数为 $1+x^2+x^4+\cdots=\frac 1{1-x^2}$。

以此类推，只选择 $t$ 的方案的生成函数为 $1+x^t+x^{2t}+\cdots=\frac 1{1-x^t}$。

于是 $a_1\le t$ 的生成函数为 $P_t(x)=\prod_{i=1}^t \frac 1{1-x^i}$，$a_1$ 无限制时生成函数为 $P(x)=\prod_{i=1}^{\infty} \frac 1{1-x^i}$。

答案即为 $[x^n]P(x)$，接下来考虑如何展开 $P(x)$。