[具体数学]第五章·二项式系数（第二部分）

第五章·二项式系数分8节，包含基本恒等式、生成函数、超几何函数、机械求和法等内容。这是笔记的第二部分，包括生成函数的内容。

至于超几何函数那块啊……呃……有点头秃……先放一放……

生成函数

对于一个无限序列 \(\langle a_0,a_1,a_2,\cdots\rangle\)，定义形式幂级数： \[ \color{purple}{A(z)=a_0+a_1z+a_2z^2+\cdots=\sum_{n\geqslant 0}a_nz^n} \] 为该序列的普通生成函数（\(\textbf{Ordinary Generating Function, OGF}\)）。

用记号 \([z^n]A(z)\) 表示 \(A(z)\) 中 \(z^n\) 的系数，即： \[ [z^n]A(z)=a_n \]

这里用 \(z\) 而非 \(x\) 是因为我们常常把 \(z\) 视为复数。

运算

设 \(\langle a_n\rangle,\langle b_n\rangle\) 的生成函数分别为 \(A(z),B(z)\)，则加减法： \[ A(z)\pm B(z)=\sum_{n\geqslant 0} (a_n\pm b_n)z^n \] 乘法： \[ \color{purple}{\begin{align} A(z)B(z)&=a_0b_0+(a_0b_1+a_1b_0)z+(a_0b_2+a_1b_1+a_2b_0)z^2+\cdots\\ &=\sum_{n\geqslant 0}z^n\sum_{k=0}^na_kb_{n-k} \end{align}} \] 即乘积的系数 \(c_n=\sum\limits_{k=0}^na_kb_{n-k}\)，称序列 \(\langle c_n \rangle\) 为序列 \(\langle a_n \rangle\) 和 \(\langle b_n \rangle\) 的卷积（convolution）。

用生成函数来发现和证明恒等式

二项式定理告诉我们：\((1+z)^r\) 是序列 \(\left\langle \binom{r}{0},\binom{r}{1},\binom{r}{2},\cdots \right\rangle\) 的生成函数，即： \[ (1+z)^r=\sum_{n\geqslant 0} \binom{r}{n}z^n \] 如果我们把 \((1+z)^r\) 和 \((1+z)^s\) 相乘，就得到了一个新的生成函数： \[ (1+z)^{r+s}=\sum_{n\geqslant 0}z^n\sum_{k=0}^n\binom{r}{k}\binom{s}{n-k} \] 对比两边 \(z^n\) 的系数，就可以得到范德蒙德卷积式： \[ \binom{r+s}{n}=\sum_{k\geqslant 0}\binom{r}{k}\binom{s}{n-k} \]

考虑 \((1-z)^r\)，它是序列 \(\left\langle\binom{r}{0},-\binom{r}{1},\binom{r}{2},\cdots\right\rangle\) 的生成函数，我们把 \((1-z)^r\) 和 \((1+z)^r\) 相乘，就得到了一个新的生成函数： \[ (1-z^2)^r=\sum_{n\geqslant 0}z^n\sum_{k=0}^n(-1)^{k}\binom{r}{k}\binom{r}{n-k} \] 对比两边 \(z^n\) 的系数，得到： \[ \color{purple}{\sum_{k=0}^n\binom{r}{k}\binom{r}{n-k}(-1)^k=(-1)^{n/2}\binom{r}{n/2}[n\;是偶数]} \] 我们发现了一个新的恒等式。

二项式系数也出现在其它一些生成函数中，以下是一个重要的恒等式（特点：下指标不动，上指标变化）： \[ \begin{align} &\color{purple}{\frac{1}{(1-z)^{n+1}}}=(1-z)^{-n-1}=\sum_{k\geqslant0}\binom{-n-1}{k}(-1)^kz^{k}=\sum_{k\geqslant 0}\binom{k+n}{k}z^k=\color{purple}{\sum_{k\geqslant 0}\binom{n+k}{n}z^k} \end{align} \] 即 \(\frac{1}{(1-z)^{n+1}}\) 是序列 \(\left\langle\binom{n+k}{n}\right\rangle\) (\(n\) 是常数，\(k\) 是下标）的生成函数。

取 \(n=0\) 得到： \[ \frac{1}{1-z}=1+z+z^2+\cdots=\sum_{k\geqslant 0}z^k \] 即 \(\frac{1}{1-z}\) 是 \(\langle1,1,\cdots\rangle\) 的生成函数。

这特别有用，因为任何其他序列和 \(\langle1,1,\cdots\rangle\) 的卷积都是前缀和的序列，即 \(c_n=\sum\limits_{k=0}^na_k\)；如此，若 \(A(z)\) 是 \(\langle a_n\rangle\) 的生成函数，则 \(\frac{A(z)}{1-z}\) 是 \(\left\langle \sum\limits_{k=0}^na_k \right\rangle\) 的生成函数。

应用：错排问题。我们之前用反演解决了，现在用生成函数来解决。

我们已知： \[ n!=\sum_{k=0}^n\binom{n}{k}D_{n-k} \] 上次是实施反演，这次两边同除 \(n!\)： \[ 1=\sum_{k=0}^n\frac{1}{k!}\frac{D_{n-k}}{(n-k)!} \] 注意 \(\sum\limits_{k=0}^n\frac{1}{k!}\frac{D_{n-k}}{(n-k)!}\) 是序列 \(\left\langle\frac{1}{k!}\right\rangle\) 和 \(\left\langle\frac{D_{n-k}}{(n-k)!}\right\rangle\) 的卷积，而 \(\left\langle\frac{1}{k!}\right\rangle\) 的生成函数就是 \(e^z\)，所以设 \(E(z)=\sum\limits_{n=0}^\infty\frac{D_n}{n!}z^n\)，那么 \(E(z)\) 和 \(e^z\) 的乘积就是 \(\frac{1}{1-z}\)，即： \[ \frac{1}{1-z}=e^zE(z) \] 于是： \[ E(z)=\frac{1}{1-z}e^{-z}=(z^0+z^1+z^2+\cdots)\left(\frac{1}{0!}z^0-\frac{1}{1!}z^1+\frac{1}{2!}z^2-\cdots\right) \] 比较系数得到： \[ \frac{D_n}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!} \] 我们反演也是得到的这个式子。

启示：应用生成函数解决问题，常常是不断在封闭形式和展开式之间来回转化；麦克劳林级数天然就是一个生成函数。

广义二项级数和广义指数级数

定义： \[ \begin{align} &\mathcal{B}_t(z)=\sum_{k\geqslant 0}(tk)^{\underline{k-1}}\frac{z^k}{k!}=\sum_{k\geqslant 0}\binom{tk}{k}\frac{z^k}{tk-k+1}\\ &\mathcal{E}_t(z)=\sum_{k\geqslant 0}(tk+1)^{k-1}\frac{z^k}{k!} \end{align} \] 将在第7章证明： \[ \begin{align} &\mathcal{B}_t(z)^{1-t}-\mathcal{B}_t(z)^{-t}=z\\ &\mathcal{E}_t(z)^{-t}\ln\mathcal{E}_t(z)=z \end{align} \] （注意 \(t=0\) 时，\(\mathcal{B}_0(z)=1+z,\,\mathcal{E}_0(z)=e^z\). ）

\(\textbf{Johann Heinrich Lambert}\) 注意到了它们满足恒等式： \[ \begin{cases}\mathcal{B}_t(z)^r=\sum\limits_{k\geqslant 0}\binom{tk+r}{k}\frac{r}{tk+r}z^k\\\mathcal{E}_t(z)^r=\sum\limits_{k\geqslant 0}r\frac{(tk+r)^{k-1}}{k!}z^k\end{cases}\quad\begin{cases}\frac{\mathcal{B}_t(z)^r}{1-t+t\mathcal{B}_t(z)^{-1}}=\sum\limits_{k\geqslant 0}\binom{tk+r}{k}z^k\\\frac{\mathcal{E}_t(z)^r}{1-zt\mathcal{E}_t(z)^t}=\sum\limits_{k\geqslant0}\frac{(tk+r)^k}{k!}z^k\end{cases} \] 我们把这两组恒等式乘在一起，就得到一些新的恒等式。例如： \[ \begin{align} \mathcal{B}_t(z)^r\frac{\mathcal{B}_t(z)^s}{1-t+t\mathcal{B}_t(z)^{-1}}&=\sum_{k\geqslant 0}\binom{tk+r}{k}\frac{r}{tk+r}z^k\sum_{j\geqslant 0}\binom{tj+s}{j}z^j\\&=\sum_{n\geqslant 0}z^n\sum_{k\geqslant 0}\binom{tk+r}{k}\frac{r}{tk+r}\binom{tn-tk+s}{n-k} \end{align} \] 同时，它又等于： \[ \frac{\mathcal{B}_t(z)^{r+s}}{1-t+t\mathcal{B}_t(z)^{-1}}=\sum_{n\geqslant 0}\binom{tn+s+r}{n}z^n \] 于是比较系数，我们得到恒等式： \[ \sum_{k\geqslant 0}\binom{tk+r}{k}\binom{tn-tk+s}{n-k}\frac{r}{tk+r}=\binom{tn+s+r}{n} \] 类似的操作可以得到其他恒等式。下表列出一般的卷积恒等式（对整数 \(n\geqslant 0\) 成立）： \[ \color{purple}{\begin{align} &\sum_{k}\binom{tk+r}{k}\binom{tn-tk+s}{n-k}\frac{r}{tk+r}=\binom{tn+s+r}{n}\\ &\sum_{k}\binom{tk+r}{k}\binom{tn-tk+s}{n-k}\frac{r}{tk+r}\cdot\frac{s}{tn-tk+s}=\binom{tn+r+s}{n}\frac{r+s}{tn+r+s}\\ &\sum_k\binom{n}{k}(tk+r)^k(tn-tk+s)^{n-k}\frac{r}{tk+r}=(tn+r+s)^n\\ &\sum_k\binom{n}{k}(tk+r)^k(tn-tk+s)^{n-k}\frac{r}{tk+r}\cdot\frac{s}{tn-tk+s}=(tn+r+s)^n\frac{r+s}{tn+r+s} \end{align}} \]

我们取 \(t\) 为一些特殊值代入，可以得到一些用途广泛、非常重要的级数： \[ \color{purple}{\begin{align} &\mathcal{B}_2(z)=\sum_k\binom{2k}{k}\frac{z^k}{1+k}=\sum_k\binom{2k+1}{k}\frac{z^k}{1+2k}=\frac{1-\sqrt{1-4z}}{2z}\\ &\mathcal{B}_{-1}(z)=\sum_k\binom{1-k}{k}\frac{z^k}{1-k}=\sum_k\binom{2k-1}{k}\frac{(-z)^k}{1-2k}=\frac{1+\sqrt{1+4z}}{2}\\ &\mathcal{B}_2(z)^r=\sum_k\binom{2k+r}{k}\frac{r}{2k+r}z^k\\ &\mathcal{B}_{-1}(z)^r=\sum_k\binom{r-k}{k}\frac{r}{r-k}z^k\\ &\frac{\mathcal{B}_2(z)^r}{\sqrt{1-4z}}=\sum_k\binom{2k+r}{k}z^k\\ &\frac{\mathcal{B}_{-1}(z)^r}{\sqrt{1+4z}}=\sum_k\binom{r-k}{k}z^k \end{align}} \] 其中，\(\mathcal{B}_2(z)\) 的系数 \(\binom{2k}{k}\frac{1}{1+k}\) 被称为 \(\textbf{Catalan}\) 数 \(C_n\)。

最后，给出一个推论，表明了 \(\mathcal{B}_{-1}(z)\) 和 \(\mathcal{B}_2(-z)\) 的关系： \[ \frac{\mathcal{B}_{-1}(z)^{n+1}-(-z)^{n+1}\mathcal{B}_2(-z)^{n+1}}{\sqrt{1+4z}}=\sum_{k\leqslant n}\binom{n-k}{k}z^k \] 证：当 \(k>n\) 时， \[ \begin{align} [z^k]\frac{(-z)^{n+1}\mathcal{B}_2(-z)^{n+1}}{\sqrt{1+4z}}&=(-1)^{n+1}[z^{k-n-1}]\frac{\mathcal{B}_2(-z)^{n+1}}{\sqrt{1+4z}}\\ &=(-1)^{n+1}(-1)^{k-n-1}[z^{k-n-1}]\frac{\mathcal{B}_2(z)^{n+1}}{\sqrt{1-4z}}&&置\;z:=-z\\ &=(-1)^k\binom{2k-n-1}{k-n-1}\\ &=(-1)^k\binom{2k-n-1}{k}\\ &=\binom{n-k}{k}\\ &=[z^k]\frac{\mathcal{B}_{-1}(z)^n}{\sqrt{1+4z}} \end{align} \] 二者抵消。

于是我们利用 \(\mathcal{B}_2(z)\) 和 \(\mathcal{B}_{-1}(z)\) 的封闭形式可以得到上述推论的封闭形式： \[ \color{purple}{\sum_{k\leqslant n}\binom{n-k}{k}z^k=\frac{1}{\sqrt{1+4z}}\left(\left(\frac{1+\sqrt{1+4z}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{1+4z}}{2}\right)^{n+1}\right)\quad,整数\;n\geqslant 0} \] 类似的，我们有： \[ \color{purple}{\sum_{k<n}\binom{n-k}{k}\frac{n}{n-k}z^k=\left(\frac{1+\sqrt{1+4z}}{2}\right)^n+\left(\frac{1-\sqrt{1+4z}}{2}\right)^n\quad,整数\;n>0} \]