《组合数学》 §2.3 学习笔记（下）

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

2.3.1 普通生成函数

事实 2.3.20

若 $f(x) = \sum_{n=0}^{\infty}a_nx^n$ ，则 $\{a_{n+1}\}_{n=0}^{\infty}$ 的普通生成函数是

$$\frac{f(x) - a_0}{x}$$

事实 2.3.21

若 $f(x) = \sum_{n=0}^{\infty}a_nx^n$ ，则 $\{a_{n+2}\}_{n=0}^{\infty}$ 的普通生成函数是

$$\frac{f(x) - a_0 - a_1x}{x^2}$$

性质 2.3.22

若 $f(x) = \sum_{n = 0}^{\infty}a_nx^n$ ，则 $\{a_{n + k}\}_{n=0}^{\infty}$ 的普通生成函数是

$$\frac{f(x) - a_0 - a_1x - \cdots - a_{k-1}x^{k-1}}{x^k}$$

事实 2.3.23

若 $f(x) = \sum_{n = 0}^{\infty}a_nx^n$ ，则 $\{na_n\}_{n=0}^{\infty}$ 的普通生成函数是

$$x\mathrm{D}f$$

这里为了方便，用 $x\mathrm{D}$ 表示 $x \frac{\rm d}{\mathrm{d}x}$ 。

推论 2.3.24

$$\{n\}_{n=0}^{\infty} \leftrightarrow x\mathrm{D}\left(\frac{1}{1 - x}\right) = \frac{x}{(1 - x)^2}$$

事实 2.3.25

若 $f(x) = \sum_{n=0}^{\infty} a_nx^n$ ，则 $\{n^ka_n\}_{n=0}^{\infty}$ 的普通生成函数是

$$(x\mathrm{D})^kf = (xD)((x\mathrm{D})^{k-1}f)$$

性质 2.3.26

若 $f(x) = \sum_{n=0}^{\infty} a_nx^n$ ，$P$ 是任一多项式，则 $\{P(n)a_n\}_{n=0}^{\infty}$ 的普通生成函数是

$$P(x\mathrm{D})f$$

例 2.3.27

求和

$$\sum_{n=0}^{\infty} \frac{n^2 + 4n + 5}{n!}$$

解 由于

$$\mathrm{e}^x = \sum_{n=0}^{\infty}\frac{1}{n!}x^n$$

故

$$((x\mathrm{D})^2 + 4(x\mathrm{D}) + 5)\mathrm{e}^x =\sum_{n=0}^{\infty}\frac{n^2 + 4n + 5}{n!}x^n$$

即

$$(x^2 + 5x + 5)\mathrm{e}^x = \sum_{n=0}^{\infty}\frac{n^2 + 4n + 5}{n!}x^n$$

在上式中，令 $x=1$ ，顺便得到

$$\sum_{n=0}^{\infty}\frac{n^2 + 4n + 5}{n!} = 11\mathrm{e}$$

性质 2.3.28

若 $f(x) = \sum_{n=0}^{\infty} a_nx^n,g(x) = \sum_{n=0}^{\infty}b_nx^n$ ，则 $f(x)g(x)$ 是数列

$$\left\{\sum_{k=0}^n a_kb_{n-k}\right\}_{n=0}^{\infty}$$

的普通生成函数。

性质 2.3.29

若 $f(x) = \sum_{n=0}^{\infty} a_nx^n$ ，$k$ 为正整数，则 $f^k(x)$ 是数列

$$\left\{\sum_{n_1 + n_2 + \dots n_k = n}a_{n_1}a_{n_2}\cdots a_{n_k}\right\}_{n=0}^{\infty}$$

的普通生成函数。

例 2.3.30

令 $f(n,k)$ 表示正整数 $n$ 写成 $k$ 个非负整数有序和的方法数，例如 $f(4,2)=5$ ，求 $f(n,k)$ 的显式表达式。

解 数列 $\{1\}_{n=0}^{\infty}$ 的普通生成函数是 $\frac{1}{1 - x}$ ，故 $\frac{1}{(1 - x)^k}$ 是数列

$$\left\{\sum_{n_1 + n_2 + \dots n_k = n}1\right\}_{n=0}^{\infty}$$

的普通生成函数。上面的数列就是 $\{f(n,k)\}_{n=0}^{\infty}$ ，从而

$$f(n, k) = [x^n]\frac{1}{(1-x)^k} = \binom{n+k-1}{n}$$

推论 2.3.31 （前缀和）

若 $f(x) = \sum_{n=0}^{\infty} a_nx^n$ ，$k$ 为正整数，则 $\frac{f(x)}{1-x}$ 是数列 $\left\{\sum_{j=0}^{n} a_j\right\}_{n=0}^{\infty}$ 的普通生成函数。

例 2.3.32 （调和级数）

$H_n$ 定义如下：

$$H_n = \begin{cases} 0&n = 0 \\[8pt] 1 + \dfrac{1}{2} + \cdots + \dfrac{1}{n} & n \ge 1 \end{cases}$$

求 $\{H_n\}_{n=0}^{\infty}$ 的普通生成函数。

解 要求的函数是 $\frac{1}{1 - x}$ 乘以 $\{\frac{1}{n}\}_{n=1}^{\infty}$ 的普通生成函数，后者显然是

$$f(x) = \sum_{n=1}^{\infty}\frac{x^n}{n}$$

由 $f^{\prime}(x) = \sum_{n=1}^{\infty}x^{n-1} = \frac{1}{1 - x}$ ，经过简单计算查表就可以得到 $f(x) = -\ln(1 - x)$ ，所以

$$\sum_{n=0}^{\infty}H_nx^n = -\frac{1}{1-x}\ln(1-x) = \frac{1}{1-x}\ln\frac{1}{1-x}$$

例 2.3.33

用硬币垒成一个“喷泉”如下：每行的硬币都连续摆在一起，除最下一行外，

每枚硬币恰好置于其下面一行的两枚硬币之间。

令 $f_n$ 为最下一行有 $n$ 枚硬币的方案数，求 $\{f_n\}_{n=0}^{\infty}$ 的普通生成函数。

解 首先 $f_0=1$ ，对 $n \ge 1$ 若只有一行，则数目为 $1$ ；若有多于一行，考虑枚举第二行有 $k$ 枚硬币，则

$$f_n = \sum_{k=1}^{n-1}(n - k)f_k + 1 = \sum_{k=1}^{n}(n - k)f_k + 1$$

令 $\{f_n\}_{n=0}^{\infty}$ 的普通生成函数为 $f(x)$ ，则

$$\begin{aligned} f(x) &= \sum_{n=0}^{\infty} f_nx^n = \sum_{n=0}^{\infty}\left(\sum_{k=1}^n(n - k)f_k + 1\right)x^n \\[6pt] &= \sum_{n=0}^{\infty} \left(\sum_{k=1}^{n}(n - k) f_k\right)x^n + \sum_{n \ge 0} 1\cdot x^n \\[6pt] &= \sum_{n=0}^{\infty}\left(\sum_{k=1}^n(n - k)f_k\right)x^n + \frac{1}{1-x} \end{aligned}$$

记 $g(x) = f(x) - 1$ ，则有 $g(x)$ 为 $g_n$ 的普通生成函数，其中 $g_0 = f_0 - 1 = 0$ 。

而当 $n \ge 1$ 时，$g_n = f_n$ ，则有

$$\sum_{k=1}^n (n - k) f_k = \sum_{k=1}^n (n - k) g_k = \sum_{k=0}^n (n - k) g_k$$

而 $\{n\}_{n=0}^{\infty}$ 的普通生成函数是 $(x\mathrm{D})\frac{1}{1-x} = \frac{x}{(1-x)^2}$ ，所以

$$\sum_{n=0}^{\infty}\left(\sum_{k=0}^n(n - k) g_k\right)x^n = \frac{x}{(1-x)^2}g(x) =\frac{x}{(1-x)^2}(f(x) - 1)$$

由

$$f(x) = \frac{x}{(1-x)^2}(f(x) - 1) + \frac{1}{1-x}$$

解得

$$f(x) = \frac{1 - 2x}{1 - 3x + x^2}$$

注 2.3.34

经过计算，可求得上例中的 $f_n$ 为

$$f_n = \frac{-1+\sqrt{5}}{2\sqrt{5}}\left(\frac{3+\sqrt{5}}{2}\right)^n + \frac{1+\sqrt{5}}{2\sqrt{5}}\left(\frac{3-\sqrt{5}}{2}\right)^n$$

2.3.2 指数型生成函数

事实 2.3.35

若 $f(x) = \sum_{n=0}^{\infty}\frac{a_n}{n!}x^n$ ，则 $\{a_{n+1}\}_{n=0}^{\infty}$ 的指数型生成函数是

$$\sum_{n=0}^{\infty} \frac{a_{n+1}}{n!}x^n = \sum_{n=1}^{\infty}\frac{na_n}{n!}x^{n-1} = f^{\prime}(x)$$

性质 2.3.36

若 $f(x) = \sum_{n=0}^{\infty}\frac{a_n}{n!}x^n$ ，则 $\{a_{n+k}\}_{n=0}^{\infty}$ 的指数型生成函数是 $\mathrm{D}^kf$ 。

例 2.3.37

题：再求 $f_n$ 。

解 令 $f(x)$ 为 $\{f_n\}_{n=0}^{\infty}$ 的指数型生成函数。性质 2.3.36 立即给出

$$f^{\prime\prime}(x) = f^{\prime}(x) + f(x)$$

解此常系数线性齐次微分方程，得到

$$f(x) = c_1\mathrm{e}^{\frac{1+\sqrt{5}}{2}x} + c_2\mathrm{e}^{\frac{1-\sqrt{5}}{2}x}$$

其中 $c_1,c_2$ 是待定系数。初始条件转化为 $f(0)=0,f^{\prime}(0)=1$ 。

代入解得 $c_1 = \frac{1}{\sqrt{5}},\,c_2 = -\frac{1}{\sqrt{5}}$ ，从而

$$f(x) = \frac{\mathrm{e}^{\frac{1+\sqrt{5}}{2}x} - \mathrm{e}^{\frac{1-\sqrt{5}}{2}x}}{\sqrt{5}}$$

最后，得

$$f_n = \left[\frac{x^n}{n!}\right]f(x) = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}}$$

事实 2.3.38

若 $f(x) = \sum_{n=0}^{\infty}\frac{a_n}{n!}x^n$ ，则 $\{na_n\}_{n=0}^{\infty}$ 的指数型生成函数是 $x\mathrm{D}f$ 。

性质 2.3.39

若 $f(x) = \sum_{n=0}^{\infty}\frac{a_n}{n!}x^n$ ，则 $\{P(n)a_n\}_{n=0}^{\infty}$ 的指数型生成函数是

$$P(x\mathrm{D})f$$

性质 2.3.40

若 $f(x) = \sum_{n=0}^{\infty}\frac{a_n}{n!}x^n,~g(x) = \sum_{n=0}^{\infty}\frac{b_n}{n!}x^n$ ，则 $f(x)g(x)$ 是

$$\left\{\sum_{k=0}^{n}\binom{n}{k}a_kb_{n-k}\right\}_{n=0}^{\infty}$$

的指数型生成函数。

例 2.3.41

回忆 Bell 数，令 $B_n$ 表示 $[n]$ 上所有划分的个数，则有

$$B_n = \sum_{k=1}^n\binom{n-1}{k-1}B_{n-k} = \sum_{i=0}^{n-1}\binom{n-1}{n-i-1}B_i \quad (\mathbf{Let}\ i = n - k)$$

所以

$$B_{n+1} = \sum_{k=0}^n\binom{n}{n-k}B_k = \sum_{k=0}^n\binom{n}{k}B_k$$

初始条件为 $B_0=1,~B_1 = 1$ 。利用上述指数型生成函数的性质，再次求解 $B_n$ 。没了。

例 2.3.42 （Catalan 括号串）& 2.3.43

详见 浅谈卡特兰数 （Catalan数）

例 2.3.44 （错排公式）

置换 $\sigma \in S_n$ 称为错位排列，如果对任意 $1 \le i \le n$ ，均有 $\sigma(i) \ne i$ 。

令 $d_n$ 表示 $S_n$ 中错位排列的总数，易得

$$n! = \sum_{k=0}^{n}\binom{n}{k}d_{n-k}$$

这促使我们考虑 $d_n$ 的指数型生成函数 $D(x) = \sum_{n=0}^{\infty}d_n\frac{x^n}{n!}$ 。

由于 $\{1\}_{n=0}^{\infty}$ 的指数型生成函数为 $\mathrm{e}^x$ ，而 $\{n!\}_{n=0}^{\infty}$ 的指数型生成函数为

$$\sum_{n\ge 0}\frac{n!}{n!}x^n = \sum_{n\ge 0}x^n = \frac{1}{1-x}$$

由前面的递推关系可得 $\frac{1}{1-x}=\mathrm{e}^xD(x)$ ，即 $D(x)=\frac{\mathrm{e}^{-x}}{1-x}$ 。

也可以利用错位排列 $d_n$ 的递推关系求解

考虑 $\sigma \in S_{n+1}$ 的最后一位 $\sigma(n + 1)$ 的取值，它有 $n$ 种可能。

• 若 $\sigma(n + 1)=i$ 且 $\sigma(i)=n+1$ ，则 $\sigma$ 为 $[n]\setminus \{i\}$ 上的一个错位排列；
• 若 $\sigma(n + 1) = i$ 但 $\sigma(i) = n + 1$ ，则用 $i$ 替代 $n+1$ 可得到 $[n]$ 上的一个错位排列。

于是

$$d_{n+1} = n(d_n + d_{n-1})$$

（注意到这个递推关系不是常系数的）所以

$$\begin{aligned} D^{\prime}(x) &= \sum_{n=0}^{\infty}\frac{d_{n+1}}{n!}x^n = \sum_{n=0}^{\infty} \frac{d_n}{(n-1)!}x^n + \sum_{n=0}^{\infty}\frac{d_{n-1}}{(n-1)!}x^n \\[6pt] &= xD^{\prime}(x) + xD(x) \end{aligned}$$

或

$$\frac{D^{\prime}(x)}{D(x)} = -1 + \frac{1}{1 - x}$$

从而 $D(x) = \frac{1}{1-x}\mathrm{e}^{-x + c}$ ，$c$ 为待定常数。

当 $x = 0$ 时，$D(0) = d_0 = 1$ ，得到 $c = 0$ ，这也求出 $D(x) = \frac{\mathrm{e}^{-x}}{1-x}$ 。

展开得到

$$D(x) = \frac{\mathrm{e}^{-x}}{1 - x} = \frac{1}{1-x}\sum_{i=0}^{\infty}\frac{(-1)^i}{i!}x^i = \sum_{n=0}^{\infty}\left(\sum_{i=0}^n\frac{(-1)^i}{i!}\right)x^n$$

所以

$$d_n = n!\sum_{i=0}^{n}\frac{(-1)^i}{i!}$$

这表明，在 $S_n$ 中任取一个置换，它是错位排列的概率为 $\frac{d_n}{n!}$ ，其极限是 $\mathrm{e}^{-1}(n \to \infty)$ 。

性质 2.3.45

若 $f(x) = \sum_{n=0}^{\infty}\frac{a_n}{n!}x^n,~g(x) = \sum_{n=0}^{\infty}\frac{b_n}{n!}x^n,~h(x)=\sum_{n=0}^{\infty}\frac{c_n}{n!}x^n$ ，则 $f(x)g(x)h(x)$ 是数列

$$\left\{\sum_{i + j + k = n,~i,j,k \ge 0}\binom{n}{i,j,k}a_ib_jc_k\right\}_{n=0}^{\infty}$$

的指数型生成函数。

性质 2.3.46

若 $f(x) = \sum_{n=0}^{\infty}\frac{a_n}{n!}x^n$ ，则 $f^{k}(x)$ 是数列

$$\left\{\sum_{n_1 + n_2 + \cdots + n_k = n,~n_i\ge 0}\binom{n}{n_1,n_2,\cdots,n_k}a_{n_1}a_{n_2}\cdots a_{n_k}\right\}_{n=0}^{\infty}$$

的指数型生成函数。

定理 2.3.47

令 $h_n$ 表示多重集 $S=\{n_1\cdot t_1,n_2\cdot t_2,\cdots,n_k\cdot t_k\}$ 的满足某种选取规则 $P$ 的 $n$–排列数

其中 $n_i \ge 0~(1 \le i \le k)$ 。记仅由 $t_i$ 组成的满足性质 $P$ 的 $n$–排列数为 $a_{i,n}$ ，

数列 $\{a_{i,n}\}_{n=0}^{\infty}$ 的指数型生成函数为 $f_i(x)~(1 \le i \le k)$ ，则数列 $\{h_n\}_{n=0}^{\infty}$ 的指数型生成函数为

$$h(x) = \prod_{i=1}^k f_i(x)$$

证明略。

注 2.3.48

一般地，若 $n_i = \infty$ ，且所循规则 $P$ 对元素 $t_i$ 的选取没有限制，则

$$f_i(x) = \mathrm{e}^x$$

若 $n_i < \infty$ ，且规则 $P$ 对元素 $t_i$ 的选取没有限制，则

$$f_i(x)=\sum_{j=0}^{n_i}\frac{x^j}{j!}$$

有时元素 $t_i$ 的选取受到限制，例如 $t_i$ 只能有大于 $1$ 的奇数个，此时 $t_i$ 满足该规则的 $n$–排列数即为

$$a_j^{(i)} = \begin{cases} 1, & j = 3,5,7,9,\cdots \\[6pt] 0, &\textbf{otherwise} \end{cases}$$

于是

$$f_i(x) = \sum_{j=1}^{\infty}\frac{x^{2j+1}}{(2j+1)!} = \frac{\mathrm{e}^x - \mathrm{e}^{-x} - 2x}{2}$$

例 2.3.49

用红、白、蓝三种颜色对 $1$ 行 $n$ 列的棋盘上所有方格进行染色。

若要求涂成红色的方格数为偶数，则有多少种涂色方法？

解 用 $h_n$ 表示这样的涂色的方法数，且设数列 $\{h_n\}_{n=0}^{\infty}$ 的指数生成函数为 $h(x)$ ，易见

$$\begin{aligned} h(x) &= \left(1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \cdots\right)\left(1 + \frac{x}{1!} + \frac{x^2}{2!} + \cdots\right)^2 \\[6pt] &=\frac{1}{2}(\mathrm{e}^x+ \mathrm{e}^{-x})(\mathrm{e}^x)^2 = \frac{1}{2}(\mathrm{e}^{3x} + \mathrm{e}^x) \\[6pt] &= \frac{1}{2}\left(\sum_{n=0}^{\infty}\frac{(3x)^n}{n!} + \sum_{n=0}^{\infty}\frac{x^n}{n!}\right) \\[6pt] &= \frac{1}{2}\sum_{n=0}^{\infty}(3^n+1)\frac{x^n}{n!} \end{aligned}$$

因此

$$h_n = \frac{3^n + 1}{2}$$

例 2.3.50

确定每位数字都是奇数且 $1$ 和 $3$ 出现偶数次的 $n$ 位数个数 $h_n$ 。

解 设 $\{h_n\}_{n=0}^{\infty}$ 的指数型生成函数为 $h(x)$ ，则

$$\begin{aligned} h(x) &= \left(1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \cdots \right)^2\left(1 + \frac{x}{1!} + \frac{x^2}{2!} + \cdots\right)^3 \\[6pt] &= \left(\frac{\mathrm{e}^x + \mathrm{e}^{-x}}{2}\right)^2\mathrm{e}^{3x} = \frac{1}{4}(\mathrm{e}^{5x} + 2\mathrm{e}^{3x} + \mathrm{e}^x) \\[6pt] &= \sum_{n=0}^{\infty} \frac{5 ^ n + 2\cdot 3^n + 1}{4}\cdot \frac{x^n}{n!} \end{aligned}$$

因此

$$h_n = \frac{5^n + 2\cdot 3^n + 1}{4}$$

2.3.3 狄利克雷生成函数

性质 2.3.51

若 $f(s) = \sum_{n=1}^{\infty}\frac{a_n}{n^s},~g(s) = \sum_{n=1}^{\infty}\frac{b_n}{n^s}$ 分别是数列 $\{a_n\}_{n=0}^{\infty}$ 和 $\{b_n\}_{n=1}^{\infty}$ 的狄利克雷生成函数，

则 $f(s)g(s)$ 是数列

$$\left\{\sum_{d \mid n} a_db_{\frac{n}{d}}\right\}_{n=1}^{\infty}$$

的狄利克雷生成函数。

性质 2.3.52

若 $f(s) = \sum_{n=1}^{\infty}\frac{a_n}{n^s}$ 是数列 $\{a_n\}_{n=1}^{\infty}$ 的狄利克雷生成函数，则 $f^k(s)$ 是数列

$$\left\{\sum_{n_1n_2\cdots n_k = n}a_{n_1}a_{n_2}\cdots a_{n_k}\right\}_{n=1}^{\infty}$$

的狄利克雷生成函数。

例 2.3.53

已知数列 $\{1\}_{n=1}^{\infty}$ 的狄利克雷生成函数是 Riemann-Zeta 函数

$$\zeta(s) = \sum_{n=1}^{\infty}\frac{1}{n^s}$$

求以 $\zeta^2(s)$ 为其狄利克雷生成函数的数列。

解 由前面的性质有

$$[n^{-s}\zeta^2(s) = \sum_{d \mid n}1 = d(n)$$

这里 $d(n)$ 是 $n$ 的正因子个数，则所求即为 $\{d(n)\}_{n=1}^{\infty}$ 。

例 2.3.54

类似地，$\zeta^k(s)$ 生成了 $n$ 的可分解为 $k$ 个有序正因子积的方法数

$(\zeta(s)-1)^k$ 生成了 $n$ 的可分解为 $k$ 个有序正因子（即大于 $1$）积的方法数。

定义 2.3.55

数论函数是指定义域为 $\mathbb{Z}^+$ 的函数。

如果数论函数 $f(x)$ 对任意互素的正整数 $m,n$ 有 $f(mn)=f(m)f(n)$ ，则称 $f(x)$ 具有积性。

由积性的定义可知，一个积性数论函数被它在素数幂上的取值唯一确定：

$$f(n) = f(p_1^{a_1})f(p_2^{a_2})\cdots f(p_r^{a_r})$$

这里 $n$ 的素因子分解为 $n = p_1^{a_1}p_2^{a_2}\cdots p_r^{a_r}$ （$p_i$ 为素数，$a_i$ 为正整数，$1 \le i \le r$）

例如，对于积性数论函数 $f(x)$ ，若知道 $p$ 是素数，$m \in \mathbb{N}^+$ 时，$f(p^{m}) = p^{2m}$ ，

则对于一切正整数 $n$ 有 $f(n) = n^2$ 。又对任意不恒为 $0$ 的积性数论函数 $f(n)$ ，显然有 $f(1) = 1$ 。

例 2.3.56

$d(n)$ 是一个积性数论函数。

定理 2.3.57

若 $f$ 是积性函数，则 $\{f(n)\}_{n=1}^{\infty}$ 的狄利克雷生成函数有下面的表达形式

$$\sum_{n=1}^{\infty}\frac{f(n)}{n^s} = \prod_{p \in \mathbb{P}}\left(\sum_{k=0}^{\infty}f(p^k)p^{-ks}\right)$$

证明略。

例 2.3.58

利用积性数论函数的上述性质，将 $\zeta(s)$ 化为乘积形式。

解 常值函数 $f : \mathbb{Z}^+ \to 1$ 是一个积性数论函数，从而

$$\zeta(s) = \prod_{p \in \mathbb{P}}\left(\sum_{k=0}^{\infty}p^{-ks}\right) = \prod_{p \in \mathbb{P}}\frac{1}{1 - p^{-s}} = \frac{1}{\prod_{p \in \mathbb{P}} (1 - p^{-s})}$$

定义 2.3.59

Möbius 函数（莫比乌斯函数）是一个积性数论函数，它在素数幂上如下定义

$$\mu(p^{a}) = \begin{cases} +1, & a = 0 \\[6pt]-1, & a = 1 \\[6pt]0, &a\ge 2 \end{cases}\quad(p \in \mathbb{P})$$

注 2.3.60

略。

事实 2.3.61

考察数列 $\{\mu(n)\}_{n=1}^{\infty}$ 的狄利克雷生成函数 $\tilde{\mu}(s)$ ，有

$$\tilde{\mu}(s) = \sum_{n=1}^{\infty} \frac{\mu(n)}{n^s} = \prod_{p \in \mathbb{P}} (1 - p^{-s})$$

从而 $\tilde{\mu}(s)\zeta(s) = 1$ ，也即

$$\frac{1}{\zeta(s)} = \sum_{n=1}^{\infty}\frac{\mu(n)}{n^s}$$

定理 2.3.62 （莫比乌斯反演）

若两数列 $\{a_{n}\}_{n=1}^{\infty},\{b_n\}_{n=1}^{\infty}$ 满足对任意 $n \ge 1$ ，有

$$a_n = \sum_{d \mid n}b_{d}$$

则对任意 $n \ge 1$ 有

$$b_n = \sum_{d\mid n}\mu\left(\frac{n}{d}\right)a_d$$

证明略。

例 2.3.63

一个由 $0$ 和 $1$ 组成的序列称为本原的，当且仅当它不能写成多于一个完全相同的子列的并置。

例如，全场为 $4$ 的 $0,1$ 序列共计 $16$ 个，其中本原序列有 $12$ 个，非本原序列有 $4$ 个，即

$$0000,\,1111,\,0101,\,1010$$

令 $f_n$ 表示长度为 $n$ 的 $0,1$ 本原序列的个数，求 $f_n$ 的显式表达式。

解 令 $a_n$ 表示长度为 $n$ 的所有 $0,1$ 序列的个数，则 $a_n = 2^n$

容易看出，对于任一长度为 $n$ 的 $0,1$ 序列，存在唯一的 $d$ 使得序列可以写成 $\frac{n}{d}$ 个长度为 $d$ 的本原序列的并置

这里 $d \mid n$ 。反之，若 $d\mid n$ ，将 $\frac{n}{d}$ 个长度为 $d$ 的本原序列并置，可得到一个长度为 $n$ 的普通 $0,1$ 序列

（该序列是本原的当且仅当 $n = d$ ）。于是当 $n \ge 1$ 时有

$$a_n = \sum_{d \mid n} f_d$$

故当 $n\ge 1$ 时，有

$$f_n = \sum_{d \mid n}\mu\left(\frac{n}{d}\right)a_d = \sum_{d\mid n}\mu\left(\frac{n}{d}\right)2^d$$

例 2.3.64 （分圆多项式）

如果复数 $\xi$ 是方程 $x^n - 1=0$ 的一个根，且满足 $\xi^m - 1\ne 0~(1 \le m \le n - 1)$

则称 $\xi$ 为 $n$ 次本原单位根。一般地，全部 $n$ 次本原单位根为

$$\left\{\left.\exp\left(\frac{2\pi ik}{n}\right) \,\right|\, 0 \le k \le n - 1,\gcd(n,k) = 1\right\}$$

熟知，以所有 $n$ 次单位根为全部根的多项式为

$$x^n - 1 = \prod_{k=0}^{n - 1}\left(x - \exp\left(\frac{2\pi ik}{n}\right)\right)$$

定义分圆多项式为以所有 $n$ 次本原单位根为全部根的多项式

$$\phi_n(x) = \prod_{0 \le k \le n-1\, \land \, \gcd(n,k)=1}\left(x - \exp\left(\frac{2\pi ik}{n}\right)\right)$$

试用 $\{x^d-1\}_{d=0}^{\infty}$ 中的多项式表示 $\phi_n(x)$ 。

解 注意到对于任一 $n$ 次单位根 $\xi$ ，都存在 $n$ 的唯一正因子 $d$ ，使得 $\xi$ 是 $d$ 次本原单位根，

从而 $\xi$ 是 $\phi_d(x)$ 的根；而对于 $n$ 的任一正因子 $d$ ，$\phi_d(x)$ 的根显然也是一个 $n$ 次单位根，

且不同的 $\phi_d(x)$ 没有相同的根，因此多项式

$$\prod_{k=0}^{n - 1}\left(x - \exp\left(\frac{2\pi ik}{n}\right)\right)=x^n - 1$$

可以分解为分圆多项式之积

$$x^n-1 = \prod_{d \mid n}\phi_d(x)$$

两边取对数，得

$$\ln(x^n - 1) = \sum_{d \mid n}\ln \phi_d(x)$$

故

$$\ln\phi_n(x) = \sum_{d \mid n}\mu\left(\frac{n}{d}\right)\ln(x^d - 1)$$

即

$$\phi_n(x) = \prod_{d \mid n}(x^d-1)^{\mu\left(\frac{n}{d}\right)}$$

由上例我们得到定理 2.3.65。

定理 2.3.65

设 $n$ 是正整数，则

$$\phi_n(x) = \prod_{d \mid n}(x^d - 1)^{\mu\left(\frac{n}{d}\right)}$$

例 2.3.66

求 $\phi_{12}(x)$ 。

解 由上述定理知

$$\begin{aligned} \phi_{12}(x) &= \prod_{d \mid 12}(x^d - 1)^{\mu\left(\frac{12}{d}\right)} \\[6pt] &= (x-1)^0(x^2-1)^1(x^3-1)^0(x^4-1)^{-1}(x^6-1)^{-1}(x^{12}-1)^1 \\[6pt] &= \frac{(x^2-1)(x^{12}-1)}{(x^4-1)(x^6-1)} \\[6pt] &= x^4 - x^2 + 1 \end{aligned}$$

注 2.3.67

虽然在分圆多项式 $\phi_n(x)$ 的定义中出现复数，

但由于 $\phi_n(x)$ 是一个整系数多项式除以一个首项系数为 $1$ 的整系数多项式，故分圆多项式也是整系数多项式。