《组合数学》 §2.3 学习笔记（上）
前言：可以参考 生成函数 学习笔记
定义 2.3.1
数列 \(\{a_n\}_{n=0}^{\infty}\) 的普通生成函数是下面的形式级数 \[ f(x) = \sum_{n=0}^{\infty} a_nx^n \]
定义 2.3.2
数列 \(\{a_n\}_{n=0}^{\infty}\) 的指数型生成函数是下面的形式级数 \[ f(x) = \sum_{n=0}^{\infty}\frac{a_n}{n!}x^n \]
定义 2.3.3
数列 \(\{a_n\}_{n=1}^{\infty}\) 的 Dirichlet 生成函数（狄利克雷生成函数）是下面的形式级数 \[ f(s) = \sum_{n=1}^{\infty} \frac{a_n}{n^s} \]
例 2.3.4
数列 \(\{1\}_{n=0}^{\infty}\) 的普通生成函数是 \[ \sum_{n=0}^{\infty}x^n = \frac{1}{1-x} \] 同时它的指数型生成函数是 \[ \sum_{n=0}^{\infty}\frac{x^n}{n!} = \mathrm{e}^x \] 而数列 \(\{1\}_{n=1}^{\infty}\) 的狄利克雷生成函数则是 \[ \sum_{n=1}^{\infty}\frac{1}{n^s} := \zeta(s) \] 这个函数就是 Riemann-Zeta 函数。
注 2.3.5
上面几个公式中的 “\(=\)” 的意义是“形式收敛”。
从解析上讲，若级数 \(A\) 与另一级数 \(B\) 分别在某个区间上收敛到同一形式，
则 \(A,B\) 必定为同一级数，从而可以通过级数 \(B\) 的表达形式来找到 \(A\) 。
因此我们一般无需考虑这些生成函数在何处收敛，而利用收敛到的闭形式（即和函数）的最终目的之一，
也是导出原始级数比较简单的表达形式，例如 \(\ln(1 + x) = \sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{n}x^n\) 。
注 2.3.6
可以定义形式级数上的运算。下面以普通生成函数为例加以说明。
若形式级数的系数在域 \(F\) 中，也称为域 \(F\) 上的形式级数。域 \(F\) 上的所有形式级数组成的集合记为 \(F[[x]]\) 。
对于形式级数 \(f(x)=\sum_{n=0}^{\infty}a_nx^n,~g(x) = \sum_{n=0}^{\infty}b_nx^n \in F[[x]]\) ，定义 \[ f(x) + g(x) = \sum_{n=0}^{\infty}(a_n + b_n)x^n \] 和 \[ f(x)g(x) = \sum_{n=0}^{\infty} c_nx^n \] 其中 \(c_n = \sum_{k=0}^{n}a_kb_{n-k}~(n \ge 0)\) 。容易证明 \(F[[x]]\) 在这样的加法和乘法下构成一个环。
进一步，对于 \(f(x)=\sum_{n=0}^{\infty}a_nx^n\) ，定义 \[ f^{\prime}(x) = \sum_{n=1}^{\infty} na_nx^{n-1} = \sum_{n=0}^{\infty}(n + 1) a_{n + 1}x^n \] 为 \(f(x)\) 的形式微商或形式导数。
如果生成函数是有限项的级数，它对应的就是一个有限项的数列，
或者说自某一项后全为零的数列，这时形式级数就是一个多项式。
定义 2.3.7
若形式级数 \(f(x) = \sum_{n=0}^{\infty}a_nx^n\) 是多项式，或形式级数 \(g(x) = \sum_{n=0}^{\infty}b_nx^n\) 满足 \(b_0=0\) ，
则可以定义 \(f(x)\) 和 \(g(x)\) 的复合 \[ f(g(x)) = \sum_{n=0}^{\infty} a_n(g(x))^n \] 当相关的复合存在，且 \(f(g(x))=g(f(x))=x\) 是，则称 \(g(x)\) 为 \(f(x)\) 的复合逆。
有时候，用 \([x^n]f(x)\) 表示 \(f(x)\) 中 \(x^n\) 的系数，用 \(\{a_n\}_{n=0}^{\infty} \leftrightarrow f(x)\) 表示数列 \(\{a_n\}_{n=0}^{\infty}\) 的生成函数是 \(f(x)\) 。
如果不加注明，则此生成函数为普通生成函数。可用生成函数来解递推关系。
例 2.3.8
设 \(n \ge 1,X_n = \{1,2,\cdots,n\}\) ，记 \(a_n\) 为 \(X_n\) 的子集个数，求 \(a_n\) 。
这道题是 2.1.1，当时给出了 \(a_n = 2a_{n-1} + [n = 0]\) ，负下标为 \(0\) 。
解 显然 \(\{a_n\}_{n=0}^{\infty}\) 的生成函数为 \[ \begin{aligned} f(x) &= \sum_{n=0}^{\infty} a_nx^n = 1 + \sum_{n=1}^{\infty}a_nx^n=1 + \sum_{n=0}^{\infty}2a_nx^{n + 1} \\[6pt]&= 1 + 2x\sum_{n=0}^{\infty}a_nx^n = 1 + 2xf(x) \end{aligned} \] 所以 \[ f(x) = \frac{1}{1 - 2x} = \sum_{n=0}^{\infty}(2x)^n = \sum_{n=0}^{\infty}2^nx^2 \] 比较系数得 \(a_n = 2^n\) 。
当然也可以用生成函数直接解决一些计数问题，如下 2.3.9 。
例 2.3.9
设有三种物体 \(a,b,c\) 。令 \(a_n\) 表示从中不重复地选取 \(n\) 种物体的方法数，
则 \(\{a_n\}_{n=0}^{\infty}\) 对应的普通生成函数可如下得出： \[ \begin{aligned} &((ax)^0 + (ax)^1)((bx)^0 + (bx)^1)((cx)^0 + (cx)^1) \\[6pt] &= (1 + ax)(1 + bx)(1 + cx) \\[6pt] &= 1 + (a + b + c)x + (ab + bc + ca)x^2 + abcx^3 \end{aligned} \] 上式中 \(x^i\) 的系数表明选取 \(i\) 种物体的选取方式。
例如 \(x^2\) 的系数为 \(ab + bc + ac\) 这三种方式。若仅仅求选取方法数，则令 \(a=b=c=1\) 即可。这时，有 \[ \{a_n\} \leftrightarrow (1 + x)^3 \] 这样我们就得到 \(a_n = \binom{3}{n}\) 。（二项式定理）
现在改变规则：设 \(a\) 可取 \(0,1\) 或 \(2\) 次，\(b\) 可取 \(0\) 或 \(1\) 次，\(c\) 可取偶数次。
令 \(b_n\) 表示选取 \(n\) 个物体的方法数，则 \(\{b_n\}_{n=0}^{\infty}\) 对应的普通生成函数即 \[ \begin{aligned} (1 + x + x^2)(1 + x)(1 + x^2 + x ^ 4 + \cdots) &= \frac{1 + x + x^2}{1 - x} \\[6pt] &= (1 + x + x^2)\sum_{n=0}^{\infty}x^n \\[6pt] &= 1 + 2x + 3\sum_{n=2}^{\infty}x^n \end{aligned} \] 从以上生成函数不难看出，当 \(n \ge 2\) 时，\(b_n = 3\) 。
接下来两个例子 2.3.10 和 2.3.12 可学习如何求出生成函数，并使之成为计数问题的有效工具
例 2.3.10
给定正整数 \(k\) ，令 \(h_n\) 表示方程 \[ x_1 + x_2 + \cdots x_k = n \] 的非负整数解的个数，我们已经知道 \[ h_n = \binom{n + k - 1}{n} \] 求 \(\{h_n\}_{n=0}^{\infty}\) 对应的普通生成函数的闭形式（封闭形式）
解 令 \(h(x)\) 为 \(\{h_n\}_{n=0}^{\infty}\) 对应的普通生成函数，则有 \[ \begin{aligned} h(x) &= \underbrace{(1 + x + x^2 + \cdots)((1 + x + x^2 + \cdots))\cdots(1 + x + x^2 + \cdots)}_{\text{k 个}} \\[8pt]&=\left(\sum_{i_1=0}^{\infty}x^{i_1}\right)\left(\sum_{i_2=0}^{\infty}x^{i_2}\right)\cdots \left(\sum_{i_k=0}^{\infty}x^{i_k}\right) \\[8pt] &= \frac{1}{(x-k)^k} \end{aligned} \]
推论 2.3.11
\[ \left\{\binom{n + k - 1}{n}\right\}_{n=0}^{\infty} \leftrightarrow \frac{1}{(1 - x)^k} \]
例 2.3.12
从数量不限的苹果🍎、香蕉🍌、橘子🍊和梨🍐中，选取 \(n\) 个水果装成一袋，且
- 选取的苹果数是偶数；
- 选取的香蕉数是 \(5\) 的倍数；
- 选取的橘子最多有 \(4\) 个；
- 选取的梨最多有 \(1\) 个。
记这样的装法有 \(h_n\) 种，求 \(h_n\) 。
解 令 \(g(x)\) 为 \(\{h_n\}_{n=0}^{\infty}\) 的普通生成函数，则 \[ \begin{aligned} g(x) &= (1 + x ^ 2 + x ^ 4 + \cdots)(1 + x^5 + x^{10} + \cdots)(1 + x + x^2 + x^3 + x^4)(1 +x) \\[6pt] &= \frac{1}{1 - x^2}\cdot \frac{1}{1 - x^5} \cdot \frac{1 - x^5}{1 - x}(1 + x) \\[6pt] &= \frac{1}{(1 - x)^2} = \sum_{n=0}^{\infty}\binom{n+1}{n} x^n \end{aligned} \] 由推论 2.3.11 得到 \(h_n = n + 1\) 。
例 2.3.13
用生成函数法求解常系数线性齐次递推关系
解 设 \(\{h_n\}_{n=0}^{\infty}\) 满足 \(k\) 阶常系数线性齐次递推关系 \[ h_n = a_1h_{n-1} + a_2h_{n-2} + \cdots + a_kh_{n-k},\quad a_j \ne 0,~ k \ge 1 \] \(\{h_n\}_{n=0}^{\infty}\) 的普通生成函数为 \(f(x) = \sum_{n=0}^{\infty}h_nx^n\) 。设 \[ k(x) = x^kg\left(\frac{1}{x}\right) = 1 - \sum_{i=1}^{k}a_ix^i \] 则 \(c(x) = k(x)f(x)\) 中 \(x^{k + r}(r \ge 0)\) 的系数为 \[ h_{k + r} - a_1h_{k+r-1} - a_2h_{k + r - 2} - \cdots - a_kh_r = 0 \] 即 \(c(x)\) 是一个次数小于 \(k\) 的多项式。
设上面的递推关系的特征方程的互不相同根为 \(q_1,q_2,\cdots,q_t\) ，而 \(q_i\) 的重数为 \(s_i~(1 \le i \le t,\sum s_i = k)\) ，则 \[ \begin{aligned} g(x) &= x^k - a_1x^{k-1} - \cdots-a_{k-1}x-a_k \\[6pt] &= (x - q_1)^{s_1}(x - q_2)^{s_2}\cdots(x - q_t)^{s_t} \end{aligned} \] 故 \[ k(x) = (1 - q_1x)^{s_1}(1 - q_2x)^{s_2}\cdots(1 - q_tx)^{s_t} \] 有理分式 \(f(x) = \frac{c(x)}{k(x)}\) 可以表示为部分分式 \[ f(x) = \sum_{i=1}^t\sum_{\ell = 1}^{s_i} \frac{\beta_{i\ell}}{(1 - q_ix)^{\ell}} \] 这里 \(\beta_{i\ell}\) 为适当的常数。由于 \[ \frac{\beta}{(1 - qx)^{\ell}} = \beta(1 - qx)^{\ell} = \beta \sum_{n=0}^{\infty}\binom{n + \ell - 1}{n}q^nx^n \] 所以 \[ \sum_{\ell = 1}^{s_i} \frac{\beta_{i\ell}}{(1 - q_ix)^{\ell}} = \sum_{\ell = 1}^{s_i}\beta_{i\ell}\sum_{n=0}^{\infty}\binom{n + l - 1}{n}q_i^nx^n = \sum_{n=0}^{\infty}(P_i(n)q_i^n)x^n \] 其中 \(P_i(n) = \sum_{\ell = 1}^{s_i} \beta_{i\ell}\binom{n + \ell - 1}{n}\) 为一个关于 \(n\) 的次数至多为 \(s_i - 1\) 的多项式。这样 \[ f(x) = \sum_{n=0}^{\infty}\left(\sum_{i=1}^tP_i(n)q_i^n\right)x^n \] 故 \(h_n = \sum_{i=1}^tP_i(n)q_i^n\) ，而 \(P_i(n)\) 的系数由初始值 \(h_0,h_1 \cdots, h_{k-1}\) 给出。
例 2.3.14 （Bell 数）
令 \(B_n\) 表示 \([n]\) 上所有划分的个数，是找到计算 \(B_n\) 的公式。
这部分有那么亿点复杂，所以不写了。公式是 \[
B_n = \frac{1}{\mathrm{e}}\sum_{k=0}^{\infty}\frac{k^n}{k!}
\]
定义 2.3.15
若形式级数 \(f(x) = \sum_{n=0}^{\infty}a_nx^n\) 与 \(g(x) = \sum_{n=0}^{\infty}b_nx^n\) 满足 \(f(x)g(x)=1\) ，则称 \(g(x)\) 为 \(f(x)\) 的乘法逆。
性质 2.3.16
形式级数 \(f(x) = \sum_{n=0}^{\infty}a_nx^n\) 有乘法逆当且仅当 \(a_0 \ne 0\) 。证明略。
性质 2.3.17
设形式级数 \(f(x) = \sum_{n=0}^{\infty} a_nx^n\) 与 \(g(x) = \sum_{n=0}^{\infty}b_nx^n\) 互为复合逆，
并且 \(a_0=0\) ，则有 \(b_0=0\) 且 \(a_1 \ne 0,\,b_1 \ne 0\) 。证明略。
事实 2.3.18
若形式级数 \(f(x) = \sum_{n=0}^{\infty} a_nx^n\) 满足 \(f^{\prime}(x) = 0\) ，则 \(f(x)\) 是常数级数 \(a_0\) 。
事实 2.3.19
若形式级数 \(f(x) = \sum_{n=0}^{\infty} a_nx^n\) 满足 \(f^{\prime}(x) = f(x)\) 则 \(f(x) = c \mathrm{e}^x\) ，其中 \(c\) 是某个常数。
