生成函数 (Generating Function) 的应用简单来说在于研究未知（通项）数列规律，用这种方法在给出递推式的情况下求出数列的通项。

对于一个数列 aaa，称f(x)=∑i=0naixif(x)=\sum_{i=0}^{n}{a_ix^i}f(x)=i=0∑n​ai​xi是数列 aaa 的 普通生成函数 (OGF)，g(x)=∑i=0nai×xii!g(x)=\sum_{i=0}^{n}{a_i\times\frac{x^i}{i!}}g(x)=i=0∑n​ai​×i!xi​是数列 aaa 的 指数生成函数 (EGF)。

我们总是认为生成函数是收敛的。

本局对战的剩余时间内，所有未加上标的求和符号，上标均为 ∞∞∞。

1. ∀n∈N∗\forall n\in\N^*∀n∈N∗ 有∑i=0nxi=1−xn+11−x\sum_{i=0}^{n}{x^i}=\frac{1-x^{n+1}}{1-x}i=0∑n​xi=1−x1−xn+1​

证明： 设 S=∑i=0nxiS=\sum_{i=0}^{n}{x^i}S=i=0∑n​xi则xS=∑i=1n+1xixS=\sum_{i=1}^{n+1}{x^i}xS=i=1∑n+1​xi所以(x−1)S=xn+1−1S=xn+1−1x−1=1−xn+11−x\begin{aligned}(x-1)S&=x^{n+1}-1\\
S&=\frac{x^{n+1}-1}{x-1}\\
&=\frac{1-x^{n+1}}{1-x}\end{aligned}(x−1)SS​=xn+1−1=x−1xn+1−1​=1−x1−xn+1​​

得证。

1. ∑i=0xi=11−x\sum_{i=0}^{}{x^i}=\frac{1}{1-x}i=0∑​xi=1−x1​

证明： 设S=∑i=0xiS=\sum_{i=0}{x^i}S=i=0∑​xi则xS=∑i=1xixS=\sum_{i=1}{x^i}xS=i=1∑​xi所以(1−x)S=1S=11−x\begin{aligned}(1-x)S&=1\\
S&=\frac{1}{1-x}\end{aligned}(1−x)SS​=1=1−x1​​

得证。

1. ∑i=0(i+1)xi=(∑i=0xi)2=1(1−x)2\sum_{i=0}^{}{(i+1)x^i}=(\sum_{i=0}^{}{x^i})^2=\frac{1}{(1-x)^2}i=0∑​(i+1)xi=(i=0∑​xi)2=(1−x)21​

证明： 先证明 ∀n∈N∗\forall n\in\N^*∀n∈N∗ 有 (∑i=0nxi)2=(∑i=0n(i+1)xi)+S…(∗)(\sum_{i=0}^{n}{x^i})^2=(\sum_{i=0}^{n}{(i+1)x^i})+S\quad…(*)(i=0∑n​xi)2=(i=0∑n​(i+1)xi)+S…(∗)其中 S=(∑i=0n−1(n−i)xn+i+1)S=(\sum_{i=0}^{n-1}{(n-i)x^{n+i+1}})S=(i=0∑n−1​(n−i)xn+i+1)

设f(x)=∑i=0xif(x)=\sum_{i=0}{x^i}f(x)=i=0∑​xi [xn]f(n)[x^n]f(n)[xn]f(n) 表示多项式 f(n)f(n)f(n) 中 xnx^nxn 项之系数。则(∑i=0nxi)2=(∑i=0nxi)⋅(∑i=0nxi)=[∑i=0n⋅(∑j,i−j∈[0,i][xj][xi−j])⋅xi]+S…(1)\begin{aligned}(\sum_{i=0}^{n}{x^i})^2&=(\sum_{i=0}^{n}{x^i})·(\sum_{i=0}^{n}{x^i})\\
&=[\sum_{i=0}^{n}·(\sum_{j,i-j\in[0,i]}{[x^j][x^{i-j}]})·x^i]+S\quad…(1)\end{aligned}(i=0∑n​xi)2​=(i=0∑n​xi)⋅(i=0∑n​xi)=[i=0∑n​⋅(j,i−j∈[0,i]∑​[xj][xi−j])⋅xi]+S…(1)​

因为 i≤ni\leq ni≤n，所以有且仅有 i+1i+1i+1 个 j∈[0,n]j\in[0,n]j∈[0,n] 使 j,i−j∈[0,i]j,i-j\in[0,i]j,i−j∈[0,i]。

所以(∑i=0nxi)2=[∑i=0n(i+1)xi]+S\begin{aligned}(\sum_{i=0}^{n}{x^i})^2&=[\sum_{i=0}^{n}{(i+1)x^i}]+S\end{aligned}(i=0∑n​xi)2​=[i=0∑n​(i+1)xi]+S​

(∗)(*)(∗) 式得证。

令 n→∞n\rightarrow\inftyn→∞ 使原命题得证。

1. ∑i=0(−x)i=11+x\sum_{i=0}^{}{(-x)^i}=\frac{1}{1+x}i=0∑​(−x)i=1+x1​

证明： 令 x=−xx=-xx=−x 并将原式代入 命题2 即可。

1. ∀m∈N∗\forall m\in\N^*∀m∈N∗ 有 1(1−x)m=∑n=0Cn+m−1m−1xn\frac{1}{(1-x)^m}=\sum_{n=0}^{}{C_{n+m-1}^{m-1}x^n}(1−x)m1​=n=0∑​Cn+m−1m−1​xn

证明： 易知 ∀m∈N∗\forall m\in\N^*∀m∈N∗ 有 (∑i=0mxi)m=1(1−x)m(\sum_{i=0}^{m}{x^i})^m=\frac{1}{(1-x)^m}(i=0∑m​xi)m=(1−x)m1​

推广 (1)(1)(1) 式，得(∑i=0nxi)m=[∑i=0n⋅(∑{aj}∈[0,n],j∈[1,m],∑aj=i∏k=0j[xak])]+S(\sum_{i=0}^{n}{x^i})^m=[\sum_{i=0}^{n}·(\sum_{\{a_j\}\in[0,n],j\in[1,m],\sum{a_j}=i}{\prod_{k=0}^{j}{[x^{a_k}]}})]+S(i=0∑n​xi)m=[i=0∑n​⋅({aj​}∈[0,n],j∈[1,m],∑aj​=i∑​k=0∏j​[xak​])]+S

而 ∀j,k\forall j,k∀j,k 都有 [ajk]=1[a_j^k]=1[ajk​]=1，所以只需证明 有且仅有 Ci+m−1m−1C_{i+m-1}^{m-1}Ci+m−1m−1​ 组 {ai}\{a_i\}{ai​} 使 ∑aj=i\sum a_j=i∑aj​=i。

考虑连续的一行 iii 个小球，你需要在 m−1m-1m−1 组相邻两个球之间各放一个隔板，将这 iii 个小球分成 mmm 份（第 jjj 份即为 aja_jaj​）。因为 aja_jaj​ 可能为零，也就是说隔板可能重叠。所以方案数为 Ci+m−1m−1C_{i+m-1}^{m-1}Ci+m−1m−1​。这样我们就证明了有且仅有 Ci+m−1m−1C_{i+m-1}^{m-1}Ci+m−1m−1​ 组 {ai}\{a_i\}{ai​} 使 ∑aj=i\sum a_j=i∑aj​=i。原命题得证。

今有 aaa 个 111 元硬币，bbb 个 222 元硬币，ccc 个 555 元硬币。求一个最小的、不能用这些硬币拼出的面值。1≤a,b,c≤1031\leq a,b,c\leq 10^31≤a,b,c≤103。

设 f(x)=∑i=0axig(x)=∑i=0bx2ih(x)=∑i=0cx5i\begin{aligned}f(x)&=\sum_{i=0}^{a}{x^i}\\
g(x)&=\sum_{i=0}^{b}{x^{2i}}\\
h(x)&=\sum_{i=0}^{c}{x^{5i}}\end{aligned}f(x)g(x)h(x)​=i=0∑a​xi=i=0∑b​x2i=i=0∑c​x5i​则 f(x)∗g(x)∗h(x)f(x)*g(x)*h(x)f(x)∗g(x)∗h(x) 各个位的系数就表示拼出这个面值的方案数，答案就是这个卷积的系数为零的最低位。

今有 A、B 两个超市，价格为 iii 的商品各有 iii 件。求从两个超市各买一个商品，恰好花 nnn 元的方案数。

生成函数f(x)=(∑i=1ixi)2=x2⋅(∑i=0(i+1)xi)2=x2(1−x)4=x2⋅∑i=0Ci+33xi\begin{aligned}f(x)&=(\sum_{i=1}{ix^i})^2\\
&=x^2·(\sum_{i=0}{(i+1)x^i})^2\\
&=\frac{x^2}{(1-x)^4}\\
&=x^2·\sum_{i=0}{C_{i+3}^{3}{x^i}}\end{aligned}f(x)​=(i=1∑​ixi)2=x2⋅(i=0∑​(i+1)xi)2=(1−x)4x2​=x2⋅i=0∑​Ci+33​xi​

所以，[xn−2](∑i=0Ci+33xi)=Cn+13[x^{n-2}](\sum_{i=0}{C_{i+3}^{3}{x^i}})=C_{n+1}^{3}[xn−2](∑i=0​Ci+33​xi)=Cn+13​。此即为答案。

求函数f(x)=∑i=0i2xif(x)=\sum_{i=0}{i^2x^i}f(x)=i=0∑​i2xi的生成函数。

由 ∀n∈N∗\forall n\in\N^*∀n∈N∗ 的 n2=∑i=1n(2i−1)n^2=\sum_{i=1}^{n}{(2i-1)}n2=i=1∑n​(2i−1)得

f(x)=∑i=0i2xi=∑i=1∑j=i(2i−1)xj=∑i=1∑j=i+1(2i−1)xj+[∑i=1(2i−1)xi]=∑i=1∑j=i+1(2i−1)xj+[2×x(1−x)2−11−x+1]\begin{aligned}f(x)&=\sum_{i=0}{i^2x^i}\\
&=\sum_{i=1}\sum_{j=i}(2i-1)x^j\\
&=\sum_{i=1}\sum_{j=i+1}(2i-1)x^j+[\sum_{i=1}(2i-1)x^i]\\
&=\sum_{i=1}\sum_{j=i+1}(2i-1)x^j+[2\times\frac{x}{(1-x)^2}-\frac{1}{1-x}+1]\end{aligned}f(x)​=i=0∑​i2xi=i=1∑​j=i∑​(2i−1)xj=i=1∑​j=i+1∑​(2i−1)xj+[i=1∑​(2i−1)xi]=i=1∑​j=i+1∑​(2i−1)xj+[2×(1−x)2x​−1−x1​+1]​

设S=2×x(1−x)2−11−x+1=x2+x(1−x)2\begin{aligned}S&=2\times\frac{x}{(1-x)^2}-\frac{1}{1-x}+1\\
&=\frac{x^2+x}{(1-x)^2}\end{aligned}S​=2×(1−x)2x​−1−x1​+1=(1−x)2x2+x​​则f(x)=∑i=1∑j=i+1(2i−1)xj+S=∑i=1(2i−1)(∑j=1xj−∑j=1ixj)+S=∑i=1(2i−1)(11−x−1−xi+1−xx−1)+S=∑i=1(2i−1)⋅xi+11−x+S=11−x(2×∑i=1i⋅xi+1−∑i=1xi+1)+S\begin{aligned}f(x)&=\sum_{i=1}\sum_{j=i+1}(2i-1)x^j+S\\
&=\sum_{i=1}(2i-1)(\sum_{j=1}x^j-\sum_{j=1}^{i}x^j)+S\\
&=\sum_{i=1}(2i-1)(\frac{1}{1-x}-1-\frac{x^{i+1}-x}{x-1})+S\\
&=\sum_{i=1}(2i-1)·\frac{x^{i+1}}{1-x}+S\\
&=\frac{1}{1-x}(2\times\sum_{i=1}i·x^{i+1}-\sum_{i=1}x^{i+1})+S\end{aligned}f(x)​=i=1∑​j=i+1∑​(2i−1)xj+S=i=1∑​(2i−1)(j=1∑​xj−j=1∑i​xj)+S=i=1∑​(2i−1)(1−x1​−1−x−1xi+1−x​)+S=i=1∑​(2i−1)⋅1−xxi+1​+S=1−x1​(2×i=1∑​i⋅xi+1−i=1∑​xi+1)+S​

而∑i=1i⋅xi+1=∑i=1(i+1)⋅xi−2∑i=1xi=1(1−x)2−1−2×x1−x=x2(1−x)2∑i=1xi+1=11−x−1−x=x21−x\begin{aligned}\sum_{i=1}{i·x^{i+1}}&=\sum_{i=1}{(i+1)·x^i}-2\sum_{i=1}x^i\\
&=\frac{1}{(1-x)^2}-1-2\times\frac{x}{1-x}\\
&=\frac{x^2}{(1-x)^2}\\
\sum_{i=1}x^{i+1}&=\frac{1}{1-x}-1-x\\
&=\frac{x^2}{1-x}\end{aligned}i=1∑​i⋅xi+1i=1∑​xi+1​=i=1∑​(i+1)⋅xi−2i=1∑​xi=(1−x)21​−1−2×1−xx​=(1−x)2x2​=1−x1​−1−x=1−xx2​​

所以f(x)=11−x(2×x2(1−x)2−x21−x)+S=x2+x(1−x)3\begin{aligned}f(x)&=\frac{1}{1-x}(2\times\frac{x^2}{(1-x)^2}-\frac{x^2}{1-x})+S\\
&=\frac{x^2+x}{(1-x)^3}\end{aligned}f(x)​=1−x1​(2×(1−x)2x2​−1−xx2​)+S=(1−x)3x2+x​​

令 h(0)=0,h(1)=1,h(n)=∑i=0n−1h(i)⋅h(n−i−1)(n≥2)h(0)=0,h(1)=1,\\
h(n)=\sum_{i=0}^{n-1}{h(i)·h(n-i-1)}\quad(n\geq2)h(0)=0,h(1)=1,h(n)=i=0∑n−1​h(i)⋅h(n−i−1)(n≥2)则 hhh 是 Catalan 数。

尝试用生成函数推导 Catalan 数的通项公式。

设 h(x)h(x)h(x) 的生成函数为 f(x)f(x)f(x)。则f(x)=∑i=0(∑j=0f(j)⋅f(i−j−1))xi+1=1+x∑i=0∑j=0i−1f(j)⋅f(i−j−1)xn−1=1+x⋅f2(x)\begin{aligned}f(x)&=\sum_{i=0}{(\sum_{j=0}f(j)·f(i-j-1))x^i}+1\\
&=1+x\sum_{i=0}{\sum_{j=0}^{i-1}{f(j)·f(i-j-1)x^{n-1}}}\\
&=1+x·f^2(x)\end{aligned}f(x)​=i=0∑​(j=0∑​f(j)⋅f(i−j−1))xi+1=1+xi=0∑​j=0∑i−1​f(j)⋅f(i−j−1)xn−1=1+x⋅f2(x)​

也就是说f(x)=1+x⋅f2(x)f(x)=1+x·f^2(x)f(x)=1+x⋅f2(x)f(x)=1±1−4x2xf(x)=\frac{1±\sqrt{1-4x}}{2x}f(x)=2x1±1−4x​​由 f(0)=1f(0)=1f(0)=1 舍去＋号，所以f(x)=1−1−4x2xf(x)=\frac{1-\sqrt{1-4x}}{2x}f(x)=2x1−1−4x​​

因为 1−4x=(1−4x)12\sqrt{1-4x}=(1-4x)^{\frac12}1−4x​=(1−4x)21​，由 广义二项式定理 得1−4x=∑i=0Ci12(−4x)i\sqrt{1-4x}=\sum_{i=0}{C_{i}^{\frac12}(-4x)^i}1−4x​=i=0∑​Ci21​​(−4x)i

而Cn12=12(12−1)⋅⋅⋅(12−n+1)n!=(−1)n−1×1×1×3×⋅⋅⋅×(2n−3)2nn!=(−1)n−1(2n−2)!22n−1n!(n−1)!1−4x=−2∑i=0(2i−2)!i!(i−1)!xif(x)=∑i=0(2i)!i!(i+1)!xi\begin{aligned}C_{n}^{\frac12}&=\frac{\frac12(\frac12-1)···(\frac12-n+1)}{n!}\\
&=(-1)^{n-1}\times\frac{1\times1\times3\times···\times(2n-3)}{2^nn!}\\
&=\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}n!(n-1)!}\\
\sqrt{1-4x}&=-2\sum_{i=0}{\frac{(2i-2)!}{i!(i-1)!}x^i}\\
f(x)&=\sum_{i=0}{\frac{(2i)!}{i!(i+1)!}x^i}\end{aligned}Cn21​​1−4x​f(x)​=n!21​(21​−1)⋅⋅⋅(21​−n+1)​=(−1)n−1×2nn!1×1×3×⋅⋅⋅×(2n−3)​=22n−1n!(n−1)!(−1)n−1(2n−2)!​=−2i=0∑​i!(i−1)!(2i−2)!​xi=i=0∑​i!(i+1)!(2i)!​xi​

所以h(n)=(2n)!n!(n+1)!h(n)=\frac{(2n)!}{n!(n+1)!}h(n)=n!(n+1)!(2n)!​

1. ∑i=0xii!=ex\sum_{i=0}{\frac{x^i}{i!}}=e^xi=0∑​i!xi​=ex
2. 偶数项求和。∑i=0x2i(2i)!=ex+e−x2\sum_{i=0}{\frac{x^{2i}}{(2i)!}}=\frac{e^x+e^{-x}}2i=0∑​(2i)!x2i​=2ex+e−x​
3. 奇数项求和。∑i=0x2i+1(2i+1)!=ex−e−x2\sum_{i=0}{\frac{x^{2i+1}}{(2i+1)!}}=\frac{e^x-e^{-x}}2i=0∑​(2i+1)!x2i+1​=2ex−e−x​

可以发现，它们与 OGF 最大的区别在于阶乘。所以，EGF 常用于解决与排列有关的问题。

用 1,2,3,41,2,3,41,2,3,4 给 nnn 个方块染色，求 1,21,21,2 颜色染的方块数为偶数的方案数。

写出 1,21,21,2 的生成函数f(x)=∑i=0x2i(2i)!f(x)=\sum_{i=0}{\frac{x^{2i}}{(2i)!}}f(x)=i=0∑​(2i)!x2i​

3,43,43,4 的生成函数g(x)=∑i=0xii!g(x)=\sum_{i=0}{\frac{x^i}{i!}}g(x)=i=0∑​i!xi​

则h(x)=f2(x)∗g2(x)=(∑i=0x2i(2i)!)2⋅(∑i=0xii!)2=(ex+e−x2)2⋅e2x=e4x+2e2x+14=14+∑i=0(4i+2n+14)xii!\begin{aligned}h(x)&=f^2(x)*g^2(x)\\
&=(\sum_{i=0}{\frac{x^{2i}}{(2i)!}})^2·(\sum_{i=0}{\frac{x^i}{i!}})^2\\
&=(\frac{e^x+e^{-x}}2)^2·e^{2x}\\
&=\frac{e^{4x}+2e^{2x}+1}4\\
&=\frac14+\sum_{i=0}(\frac{4^i+2^{n+1}}4)\frac{x^{i}}{i!}\end{aligned}h(x)​=f2(x)∗g2(x)=(i=0∑​(2i)!x2i​)2⋅(i=0∑​i!xi​)2=(2ex+e−x​)2⋅e2x=4e4x+2e2x+1​=41​+i=0∑​(44i+2n+1​)i!xi​​

所以[xn]h(x)=4n+2n+14[x^n]h(x)=\frac{4^n+2^{n+1}}4[xn]h(x)=44n+2n+1​

（To Be Continued）