形如 $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$

先考虑 $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)$。

这里给出五边形数定理和证明。

$$\prod_{i=1}^{\infty}\left(1-x^i\right)=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$$

于是有 $P(x)\prod_{i=1}^{\infty}\left(1-x^i\right)=1$，展开

$$ \begin{matrix} P(x) & p_0 & p_1x & p_2x^2 & p_3x^3 & p_4x^4 & p_5x^5 &\cdots \\ -xP(x)& & -p_0x & -p_1x^2 & -p_2x^3 & -p_3x^4 & -p_4x^5 &\cdots \\ -x^2P(x)& & & -p_0x^2 & -p_1x^3 & -p_2x^4 & -p_3x^5 &\cdots \\ x^5P(x)& & & & & & p_0x^5 &\cdots \\ \cdots \\ \prod_{i=1}^{\infty}\left(1-x^i\right)P(x) & 1 & 0x & 0x^2 & 0x^3 & 0x^4 & 0x^5 &\cdots \end{matrix} $$

于是 $p_n=[n==0]+p_{n-1}+p{n-2}-p_{n-5}-p_{n-7}+\cdots$。

牛客暑期多校(第五场) C 题

已知 $\sum_{i=1}^k a_i=n,\sum_{i=1}^k b_i=m,P=\sum_{i=1}^k \min(a_i,b_i)$，$\sum_{a,b}P$。

令 $F(x)=\sum_{i=1,j=1}^{\infty} x^iy_j$，于是答案为 $[x^ny^m]F^k(x)$。

考虑求出 $F(x)$ 的封闭式。

$$ \begin{equation}\begin{split} F(x)&=xy &+xy^2 &+xy^3 &+xy^4+\cdots \\ &+x^2y &+2x^2y^2 &+2x^2y^3 &+2x^2y^4+\cdots \\ &+x^3y &+2x^3y^2 &+3x^3y^3 &+3x^3y^4+\cdots \end{split}\end{equation} $$ 先想办法将系数化为 $1$，考虑相邻行之间错位相减，有

$$ \begin{equation}\begin{split} (1-x)F(x)&=xy &+xy^2 &+xy^3 &+xy^4+\cdots \\ & &+x^2y^2 &+x^2y^3 &+x^2y^4+\cdots \\ & & &+x^3y^3 &+x^3y^4+\cdots \end{split}\end{equation} $$ 然后发现每行均成为等比数列，直接求和得 $$(1-x)F(x)=\frac {xy}{1-y}+\frac{x^2y^2}{1-y}+\frac{x^3y^3}{1-y}+\cdots $$ 发现结果仍然为等比数列，继续求和得 $$(1-x)F(x)=\frac {xy}{(1-y)(1-xy)}$$ 于是有 $$ \begin{equation}\begin{split} F^k(x)&=\frac {x^ky^k}{(1-x)^k(1-y)^k(1-xy)^k} \\ &=x^ky^k\sum_{a=0,b=0,c=0}^{\infty} \end{split}\end{equation} $$