定义

首先通过一个例子来说明什么是生成函数。

生成函数是组合数学中的一个概念，对于一个数列 $a_0,a_1,a_2,…,a_k$ ，即 $f(i) = a_i$ (f是离散函数) 。可以构造一个 $f$ 的生成函数，使 $x^k$ 的系数是 $f(k)$ 。（至于问什么这么构造，是因为幂函数的良好性质： $x^ax^b = x^{a+b}$ ，这样设可以良好的契合许多组合数学中面临的许多问题） $g(x) = f(0)+f(1)x+f(2)x^2+...+f(k)x^k+...$ 当然，构造出这么个东西肯定是有用的，下面看一个具体的例子： $f(i) = 1$ ，有生成函数： $g(x) = 1+x+x^2+...$ 明显当满足一定条件时 $g(x)$ 可以写成 $g(x) = \frac{1}{1-x} \quad (-1<x<1)$ 因为 $g(x)$ 是构造出来的，实际上 $x$ 并没有什么实际意义，在研究生成函数时默认级数都是收敛的。于是就可以说 $f(n) = 1$ 的生成函数是 $g(x) = \frac{1}{1-x}$ 。

可以发现有的生成函数可以用一个较短的形式表示。找到较短的式子之后可以通过二项式展开得到 $x^k$ 的系数 $a_k$ .

下面说一下二项式展开相关内容

广义二项式定理

也称牛顿二项式定理 $(x+y)^n = \sum_{k=0}^{\infty} C_n^k x^{n} y^{n-k} \quad (n为任意实数)$ 设 $z = \frac{x}{y}$ 则： $(x+y)^n=y^n(1+z)^n$ ，等价于求 $(1+z)^n$

$\begin{align*} (1+z)^n &= C_n^0z^0 + C_n^1z^1 + ... + C_n^nz^n + C_n^{n+1}z^{n+1} + ...\\ &= \sum_{k=0}^{\infty} C_n^kz^k \end{align*}$ 用 $-n$ 代替 $n$ : $\left(\begin{array}{c}{n} \\ {k}\end{array}\right)=\left(\begin{array}{c}{-n} \\ {k}\end{array}\right)=\frac{-n(-n-1) \ldots(-n-k+1)}{k !}=(-1)^{k}\left(\begin{array}{c}{n+k-1} \\ {k}\end{array}\right)$ 所以有： $\begin{align*} (1+z)^{-n}&=\frac{1}{(1+z)^{n}}=\sum_{k=0}^{\infty}(-1)^{k}\left(\begin{array}{l}{n+k-1} \\ {k}\end{array}\right) z^{k}\\ (1-z)^{-n}&=\frac{1}{(1-z)^{n}}=\sum_{k=0}^{\infty}\left(\begin{array}{l}{n+k-1} \\ {k}\end{array}\right) z^{k} \end{align*}$ $n=1$ 时有 : $\begin{aligned} (1+z)^{-1}&= \frac{1}{(1+z)}=\sum_{k=0}^{\infty}(-1)^{k} z^{k} \\ (1-z)^{-1}&=\frac{1}{(1-z)} =\sum_{k=0}^{\infty} z^{k} \end{aligned}$ 广义组合数：

$\begin{align*} C_{k}^{i} &= \frac{k(k-1)(k-2)…(k-i+1)}{i!}\\ C_4^6 &= \frac{4*3*2*1*0*(-1)}{6!}=0 \\ C_{-1.4}^2 &= \frac{(-1.4)*(-2.4)}{2!}=1.68 \end{align*}$

常用公式

$\begin{align*} \frac{1}{1-x} &= 1+x+x^2+x^3+... \\ \frac{1}{1-x^k} &= 1+x^k+x^{2k}+x^{3k}+...\\ \frac{1}{1-ax} &= 1+ax+a^2x^2+a^3x^3+... \\ \frac{1}{(1-x)^{n}} &= \sum_{k=0}^{\infty}C_{n+k-1}^{k} x^{k}\\ \\ \frac{1}{(1+x)^{n}}&=\sum_{k=0}^{\infty}(-1)^kC_{n+k-1}^{k} x^{k}\\ \frac{1}{1+x} &= 1-x+x^2-x^3+... \\ \end{align*}$

经典应用

例一

求 $n = x_1+x_2+…+x_k$ 有多少非负整数解。

把每组解都加1 ： $n+k = x_1+x_2+…+x_k$

把 $n+k$ 看作 $n+k$ 个东西，至多分成 $k$ 份就是在 $n+k-1$ 个空格中间插入 $k-1$ 个木板，总方案数就是 $C_{n+k-1}^{k-1} = C_{n+k-1}^{n}$ ，有生成函数 $g(x) = \frac{1}{(1-x)^k}$ 也相当于 $x_i$ 可以取 $0$ ~ $n$ 个 $1$ 组成，表示为 $(1+x^1+x^2+…)$ 。总情况就是 $g(x) = (1+x^1+x^2+x^3+...)^k = \frac{1}{(1-x)^k}$ 其中 $x^n$ 的系数就是答案（因为它的这个系数是由原式完全展开后 $k$ 个指数加起来恰好等于 $n$ 的项合并起来得到的），即 $C_{n+k-1}^{n}$

##　例二

我们要从苹果、香蕉、橘子和梨中拿一些水果出来，要求苹果只能拿偶数个，香蕉的个数要是5的倍数，橘子最多拿4个，梨要么不拿，要么只能拿一个。问按这样的要求拿 $n$ 个水果的方案数。

有： $\begin{align*} g(x) &= (1+x^2+x^4+...)(1+x^5+x^{10}+...)(1+x^1+x^2+x^3+x^4)(1+x^1)\\ &= \frac{1}{1-x^2}\frac{1}{1-x^5}\frac{1-x^5}{1-x}(1+x)\quad \quad (1-x)(1+x^1+x^2+x^3+x^4) = (1-x^5) \\ &= \frac{1}{(1-x)^2} \end{align*}$ 答案就是 $x^n$ 的系数 $C_{n+1}^{1}$

例三

整数拆分问题、五边形定理

例四

用母函数推斐波那契递推式的通项公式。已知 $f(n) = f(n-1)+f(n-2)$

$\begin{align*} G(x)&=f(0)+f(1) x+f(2) x^{2}+f(3) x^{3}+\ldots\\ x G(x)&=f(0) x+f(1) x^{2}+\ldots\\ x^{2} G(x)&=f(0) x^{2}+\ldots\\ \therefore G(x)&=x G(x)+x^{2} G(x)+x\\ G(x) &= \frac{x}{1-x-x^2} \\ &= \frac{x}{x^2(x^{-2}-x^{-1}-1)} \\ &= \frac{x}{x^2(m^2-m-1)} \quad (m=x^{-1})\\ &= \frac{x}{x^2(m-\alpha)(m-\beta)} \quad (\alpha = \frac{1+\sqrt{5}}{2},\beta=\frac{1-\sqrt{5}}{2})\\ &= \frac{x}{(1-\alpha x)(1-\beta x)} \\ &= \frac{A}{1-\alpha x} + \frac{B}{1-\beta x} \quad (A=\frac{1}{\sqrt{5}},B=-\frac{1}{\sqrt{5}})\\ &= A(1+\alpha x+\alpha^2x^2+...)+B(1+\beta x+\beta^2x^2+...) \\ &= \sum_{n=0}^{\infty}(A\alpha^n+B\beta^n)x^n \end{align*}$

所以通项公式 $F(n) = A\alpha^n+B\beta^n = \frac{1}{\sqrt{5}}\left( (\frac{1+\sqrt{5}}{2})^n+(\frac{1-\sqrt{5}}{2})^n\right)$