引言
组合计数问题是信息学竞赛中常见的一类问题，而生成函数往往是解决这类问题的重要工具。
上面这句话出自2015年金策的论文，这篇论文写的非常系统，推荐阅读。
本文则是偏向于推导和总结，分成组合数学部分和多项式全家桶 一点都不全 部分，分别讲解生成函数在解决组合计数问题的方法及技巧。
组合数学
基础概念
生成函数
生成函数就是一列用来展示一串数字的挂衣架。（赫伯特·维尔夫）
在数学中，某个序列 \({\displaystyle (a_{n})_{n\in \mathbb {N} }}\) 的母函数（又称生成函数，英语：Generating function）是一种形式幂级数，其每一项系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。（*）
看完上面的解释，相信初次接触生成函数的读者也对它有了一定的了解 （扯吧 。生成函数按实现功能可以分成两类：普通型生成函数、指数型生成函数。
普通型生成函数(OGF)
对于一个给定的数列 \(\{a_n\}\) ，定义它的普通型生成函数 \(G(x)\) 为
\[ G(x)=\sum_{n=0}^{+\infty}a_nx^n \]
如果这个数列是不是无穷数列，那么比最后一项高的项都为 \(0\) 。
指数型生成函数(EGF)
对于一个给定的数列 \(\{a_n\}\) ，定义它的指数型生成函数 \(G(x)\) 为
\[ G(x)=\sum_{n=0}^{+\infty}{a_n\over n!}x^n \]
如果这个数列是不是无穷数列，那么比最后一项高的项都为 \(0\) 。
生成函数说白了就是把一个数列摆在一个形式幂级数上，而形式幂级数就是上面那个写成函数样子的 \(G(x)\) ，注意，它真的就只是一个形式，那个变量 \(x\) 不可能真的带一个数进去算。如果拿挂衣架做比喻的话，那 \(x\) 的不同幂次就相当于挂衣架上的一个一个钩子，数列 \(\{a_n\}\) 就是一件一件的衣服。钩子把一件一件衣服挂在挂衣架上，就是生成函数。
我们不妨用几道烂大街的数学题来看一下生成函数这个东西的作用。
例子
-
（例题 1-1-1）有 \(1g\) 砝码 \(2\) 枚，\(2g\) 砝码 \(3\) 枚，\(3g\) 砝码一枚，相同质量砝码之间没有区别，问称出每种质量的方案数。
解：
考虑生成函数，设 \(x\) 的指数为砝码的质量，可以写出普通型生成函数如下
\[
\begin{align*}
F(x)&=(1 + x + x^2)(1 + x^2 + x^4 + x^6)(1+x^3)\\
&= 1 + x + 2 x^2 + 2 x^3 + 3 x^4 + 3 x^5 + 3 x^6 + 3 x^7 + 2 x^8 + 2 x^9 + x^{10} + x^{11}
\end{align*}
\]
其中每一个括号里的内容代表每一种质量的砝码，以第一个括号为例，\(1\)（即 \(x^0\) ）代表不取 \(1g\)
砝码，\(x\) 代表取 \(1\) 个 \(1g\) 砝码，\(x^2\) 代表取 \(2\) 个 \(1g\) 砝码，其他同理。
-
（例题 1-1-2）你有数字 \(1\) 两个，数字 \(2\) 三个， 数字 \(3\) 一个，问选出一个、两个、三个……数字的方案数。
解：
考虑生成函数，设 \(x\) 的指数为数字的个数，可以写出普通型生成函数如下
\[
\begin{align*}
F(x)&=(1+x+x^2)(1+x+x^2+x^3)(1+x)\\
&= 1 + 3x + 5x^2 + 6 x^3 + 5x^4 + 3x^5 + x^6
\end{align*}
\]
本题的题面和上道题有点像，但是要求的东西不同，上道题要求的是每种质量和的方案数（即数字总和），而这道题是数字个数，定义状态不同，故生成函数不同。
这道题其实是为了引出下面这道指数型生成函数的例题。
-
（例题 1-1-3）你有数字 \(1\) 两个，数字 \(2\) 三个， 数字 \(3\) 一个，问组成一位数、两位数、三位数……的方案数。
解：
考虑生成函数，设 \(x\) 的指数为数字的个数，可以写出指数型生成函数如下
\[
\begin{align*}
F(x)&=({1\over 0!}+{1\over 1!}x+{1\over 2!}x^2)({1\over 0!}+{1\over 1!}x+{1\over 2!}x^2+{1\over 3!}x^3)({1\over 0!}+{1\over 1!}x)\\
&={1 \over 0!} + {3 \over 1!} x + {8 \over 2!} x^2 + {19 \over 3!} x^3 + {38 \over 4!} x^4 + {60 \over 5!} x^5 + {60 \over 6!} x^6
\end{align*}
\]
指数型生成函数可能刚开始有点难以理解，初学者可能会发出这样的疑问：这个东西不就是 \(x^n\) 下面加了一个 \(n!\) 吗？是的，形式上就是这样的，在编程中，运算时也要把它转成普通型运算，再转成指数型展示。但是，与上面的问题对比一下，就不难发现一个规律：
普通型生成函数解决的是组合问题（无标号），指数型生成函数解决的是排列问题（有标号）。
好吧，这里面也没什么大道理，让我们观察其中一项的计算过程，以 \(x^3\) 为例，我们看一下那个 \(19\) 是怎么来的。
\[
\begin{align*}
{19\over 3!}&={1\over 2!\cdot 1!\cdot 0!}+{1\over 2!\cdot 0!\cdot 1!}+{1\over 1!\cdot 2!\cdot 0!}+{1\over 1!\cdot 1!\cdot 1!}+{1\over 0!\cdot 3!\cdot 0!}+{1\over 0!\cdot 2!\cdot 1!}\\
19&={3!\over 2!\cdot 1!\cdot 0!}+{3!\over 2!\cdot 0!\cdot 1!}+{3!\over 1!\cdot 2!\cdot 0!}+{3!\over 1!\cdot 1!\cdot 1!}+{3!\over 0!\cdot 3!\cdot 0!}+{3!\over 0!\cdot 2!\cdot 1!}\\
19&={3\choose 2\quad 1\quad 0}+{3\choose 2\quad 0\quad 1}+{3\choose 1\quad 2\quad 0}+{3\choose 1\quad 1\quad 1}+{3\choose 0\quad 3\quad 0}+{3\choose 0\quad 2\quad 1}
\end{align*}
\]
式子变一变，就变成了一个多重元素全排列的形式，例题 1-1-2 是对一样的数列构造一个普通型生成函数，\([x^3]=6\) ，（\([x^n]\) 表示取多项式中次数为 \(n\) 的项的系数）而 \(\displaystyle {19\over 3!}\) 展开也有 \(6\) 项，只是每一项多乘了排列数罢了。
更形式的说，设原题三个括号中的生成函数分别为 \(A(x),B(x),C(x)\)，有
\[
F(x)={\displaystyle\large\sum_{n=0}^{+\infty}}\sum_{i=0}^{+\infty}\sum_{j=0}^{+\infty}\sum_{k=0}^{+\infty}[n=i+j+k]{n\choose i\quad j \quad k}a_ib_jc_kx^n
\]
对于有标号的组合对象，我们在转移时还要考虑不同的标号排列，于是我们在分母上填了阶乘，这样就可以帮助我们转移了。接下来，我们来看一下这个叫组合对象的基础概念。
组合对象
组合计数问题一般定义了一类组合对象 \(A\) ,它可能是满足某一类性质的树、图、串等对象的集合；其中每个对象 \(a \in A\) 都被赋予了一个大小 \({\rm size}(a) \in\mathbb N\)，它可能代表节点数，序列长度等。对于某个固定的 \(n\)，满足 \({\rm size}(a)=n\) 的对象是有限的，记作 \(A_n\) 。我们的任务通常为求出 \(A_n\) 的数值。
根据不同问题的要求，组合对象可以分为有标号和无标号两类。
（论文）
比较概念性的东西，为了加深对组合意义的理解。
在例题1-1-1中，不同砝码组合构成的集合就是我们要研究的组合对象，每一种砝码组合就是一个对象，对象 \(a\) 的 \(\rm size\) 定义为这个砝码组合的质量和，\(A_n\) 表示质量和为 \(n\) 的砝码组合的方案数，该组合对象属于无标号组合对象；
在例题1-1-3中，不同 \(n\) 位数（ \(n\) 个数字的排列）构成的集合就是我们的组合对象，一个 \(n\) 位数就是一个对象，对象 \(a\) 的 \(\rm size\) 定义为数的位数，\(A_n\) 表示构成 \(n\) 位数的方案数，该组合对象属于有标号组合对象。
稍微理解一下“组合对象”这个名词就好。
基础公式
仅仅只是表示成几个式子的乘积只是生成函数最基本的部分，利用形式幂级数的变形进行推导才是比较有研究价值的地方，接下来，我们来展示一些基础而重要的公式并给出其应用。
公式
- 公式 \(\rm I\)
\[ \displaystyle (1-x)^{-1} = \sum_{n=0}^{+\infty}x^n\\ \]
也被称作无穷递缩等比数列求和公式，由于收敛性，\(x\in(0,1)\) 时式子成立，但由于本文讲的是生成函数，写出来的但式子是形式幂级数，所以 \(x\) 不能代具体的数。
把左边的分母乘到右边去就可以得证，或者直接套用等比数列求和公式证明。
- 公式 \(\rm II\)
\[ \quad\displaystyle (1-x)^{-k} = \sum_{n=0}^\infty{n+k-1\choose k-1}x^n = \sum_{n=0}^\infty{n+k-1\choose n}x^n \]
可以由公式 \({\rm I}\) 两边同求 \(k-1\) 次导，再同除以 \((k-1)!\) 得到。 也可以把式子转化为 \({\big(}(1-x)^{-1}{\big)}^k\) ，用隔板法证明。
- 公式 \(\rm{III}\) （广义二项式定理）
\[
(x + y)^\alpha = \sum_{i=0}^{+\infty}{\alpha \choose i}x^iy^{\alpha -i}
\]
其中 \(\displaystyle{\alpha \choose k}={\alpha(\alpha - 1)\cdots(\alpha - k + 1)\over k!}={\alpha^{{\underline k}}\over k!}\)
可以利用广义二项式定理推导公式 \(\rm{I}\) 和公式 \(\rm{II}\) 。
- 公式 \(\rm{IV}\) （泰勒展开）
\[ f(x)=\sum_{n=0}^\infty {f^{(n)}(a)\over n!}(x-a)^n \]
表示 \(f(x)\) 在 \(x=a\) 处的泰勒展开，其中 \(f^{(n)}\) 表示 \(f\) 的 \(n\) 阶导函数，其中 \(a=0\) 的情况被称作麦克劳林展开，形式如下：
\[
f(x)=\sum_{n=0}^\infty {f^{(n)}(0)\over n!}x^n
\]
- 公式 \(\rm V\)
\[ \displaystyle e^x = \sum_{n=0}^{+\infty}{1\over n!}x^n\\ \]
直接套用麦克劳林展开公式就可以得到，注意 \(e^x\) 的导数是它本身。