《组_

《组合数学》 §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$ 是某个常数。

---

传送门：《组合数学》 §2.3 学习笔记（下）