【学习笔记】生成函数入门

引入

你一定学过二项式定理，即

$(a+b)^n = \sum\limits_{i=0}^n \binom{n}{i} a^i b^{n-i}$

你也大概率做过一道题：求值：

$\binom n 0 + \binom n 1 +\binom n 2 + \cdots \tag{1}$

事实上，只需要展开 $(1+1)^n$ 就可以得到这个序列（注意这是一个无限序列，第 $n+1$ 项以后都是 $0$）。那么读者不难想到是不是也可以用像 $(1+1)^n$ 一样的一个函数来表示一个序列呢？于是我们引入了生成函数。

从二项式系数开始

对于一个无限序列 $\left<a_0, a_1, a_2 \cdots \right>$，我们用一个幂级数来表示它：

$G(x) = a_0 + a_1 x + a_2 x^2 + \cdots = \sum\limits_{k \ge 0} a_k x^k \tag{2}$

即，如果把该幂级数 $G(x)=\sum\limits_{k \ge 0} a_k x^k$ 的 $n$ 次项的系数为 $G(x)_n$（这是自己发明的完全不正式的记法） 即 $G(x)_n = a_n$，那么 $G(x)_n$ 就是该无限序列的第 $n$ 项。称 $G(x)$ 为序列 $a$ 的生成函数。

举例来说，式 $(1)$ 的生成函数即为 $G(x) = \sum\limits_{k\ge 0} \binom{n}{k} x^k$。它的封闭形式为 $(1+x)^n$

现在，我们考虑两个生成函数 $G(x)$ 与 $F(x)$ 的乘积 $H(x)$。大家都学过多项式的乘法，于是很显然，两个生成函数的乘积的某一项的系数是一个卷积的形式，容易写出 $H(x)_n$ 的式子：

$H(x)_n = \sum\limits_{k=0}^n G(x)_k \cdot F(x)_{n-k}$

节标题叫“从二项式系数开始”，所以我们现在开始讨论二项式系数（组合数）。

类似于 $(1)$，令

$G(x) = (1+x)^n = \sum\limits_{k\ge 0} \binom{n}{k} x^k \\ F(x) = (1+x)^m = \sum\limits_{k\ge 0} \binom{m}{k} x^k \\ H(x) = G(x) \cdot F(x) = (1+x)^{n+m} = \sum\limits_{k\ge 0} \binom{n+m}{k} x^k$

考虑 $F(x) \cdot G(x)$ 的展开式（卷积）与 $H(x)$ 的第 $n$ 项相等，我们得到

$\sum\limits_{k=0}^n \binom n k \binom m {n-k} = \binom{n+m}{n} \tag 3$

即范德蒙德卷积公式。这个公式曾经在另一篇学习笔记 【学习笔记】组合数学 中出现过，并附有组合推理的证明。

练习：仿照该过程，证明：

$\sum\limits_{k=0}^n \binom m k \binom m {n-k} (-1)^k = (-1)^{{n/2}} \binom m {n/2} [\ n\text{ is even }]$

提示：设 $G(x) = (1-x)^m$，$F(x) = (1+x)^m$

鸽了，暑假再学