《组合数学》 §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} \]