4.9　习题解答Solutions to exercises

本页为译文 + 高中讲解合一：黑色正文为原书解答的忠实翻译；彩色框（分步推演 / 例 / 目标）与配图为面向高中生的详解，逐步把原书省略的步骤补全，并配具体数字与图，不用比喻。

习题 1　降位与升位的对称

回忆 \(A(n,k)\) 是长度为 \(n\)、恰有 \(k-1\) 个降位的排列个数。若 \(p=p_1p_2\cdots p_n\) 有 \(k-1\) 个降位，则它的反序（reverse） \(p^r=p_np_{n-1}\cdots p_1\) 就有 \(k-1\) 个升位（ascent），于是它有 \((n-1)-(k-1)=n-k\) 个降位。换句话说，"取反序"是从 \(A(n,k)\) 所计的排列集到 \(A(n,n+1-k)\) 所计的排列集的一个双射（bijection）。

另一种做法是取补（complement）：对 \(p=p_1p_2\cdots p_n\)，定义 \(p^c\) 的第 \(i\) 项为 \(n+1-p_i\)。若 \(p\) 有 \(k-1\) 个降位，则它的补 \(p^c\) 有 \(k-1\) 个升位，证明同上完成。

1. 一个长为 \(n\) 的排列共有 \(n-1\) 个相邻位置 \((1,2),(2,3),\dots,(n-1,n)\)。每个相邻位置要么是升位（\(p_i<p_{i+1}\)），要么是降位（\(p_i>p_{i+1}\)），二者必居其一。所以 升位数 + 降位数 \(=n-1\)。
2. 反序把序列从右往左读。原来的相邻对 \((p_i,p_{i+1})\) 在反序里变成 \((p_{i+1},p_i)\)，大小关系正好颠倒：原来是升位就变降位，原来是降位就变升位。所以反序把 \(k-1\) 个降位变成 \(k-1\) 个升位。
3. 反序的降位数 \(=(n-1)-(\text{反序的升位数})=(n-1)-(k-1)=n-k\)。也就是说 \(p^r\) 被 \(A(n,n-k+1)\) 计数（因为 \(A(n,m)\) 对应 \(m-1\) 个降位，取 \(m-1=n-k\) 即 \(m=n+1-k\)）。
4. 反序操作做两次回到原排列，故它是一一对应，于是 \(A(n,k)=A(n,n+1-k)\)。

习题 2　降位集只含一个点的排列

在被 \(\alpha(\{i\})\) 计数的排列中，前 \(i\) 个元素必须构成递增序列，后 \(n-i\) 个元素也必须构成递增序列。因此，一旦知道了前 \(i\) 个元素组成的集合，整个排列就被确定。这给出 \(\alpha(\{i\})=\binom{n}{i}\)。容易用计算证明：对固定的 \(n\)，\(\binom{n}{i}\) 在 \(i=\lfloor n/2\rfloor\) 处取得最大值（若不信，见命题 6.39）。

1. \(\alpha(\{i\})\) 数的是"降位只可能出现在第 \(i\) 个位置"的排列。也就是说，第 \(1\) 到第 \(i-1\) 个相邻位置都不是降位（即前 \(i\) 项递增），第 \(i+1\) 到第 \(n-1\) 个相邻位置也都不是降位（即后 \(n-i\) 项递增）。
2. 把 \(\{1,2,\dots,n\}\) 任选 \(i\) 个数放前段，剩下 \(n-i\) 个放后段；每段内部因为必须递增，排法唯一。所以排列个数 = 选前 \(i\) 个数的方法数 \(=\binom{n}{i}\)。

习题 3　降位集含于 \(\{3,7\}\) 的长 10 排列

设 \(\pi=\{B_1,B_2,B_3\}\) 是 \([10]\) 的任一有序划分，其中块 \(B_1,B_2,B_3\) 的大小分别为 \(3,4,3\)。把每块的元素按递增排列，再依次写下 \(B_1\)、\(B_2\)、\(B_3\) 的元素。显然得到的排列降位集含于 \(\{3,7\}\)（因为每块内部递增）。也显然每个这样的排列恰好出现一次。所以我们只需求这种划分 \(\pi\) 的个数。这不难，因为选 \(B_1\) 有 \(\binom{10}{3}\) 种，再选 \(B_2\) 有 \(\binom74\) 种，而 \(B_3\) 没有选择余地。于是由乘法原理 \[\alpha(\{3,7\})=\binom{10}{3}\cdot\binom{7}{4}.\]

1. 降位只能出现在位置 3 和 7，等于说排列被切成三段：第 1–3 位、第 4–7 位、第 8–10 位，每段内部递增。这正好对应把 \([10]\) 分成大小 \(3,4,3\) 的三个有序块，每块内部按从小到大写。
2. 选第一段的 3 个数：\(\binom{10}{3}=120\) 种。
3. 从剩下 7 个数里选第二段的 4 个数：\(\binom74=35\) 种。
4. 剩下 3 个数自动成为第三段，没有选择。
5. 每段写法唯一，故总数 \(=120\times35=4200\)，即 \(\binom{10}{3}\binom74\)。

习题 4　降位集含于一般集合 \(S\)

设 \(s_i\) 已按递增排列（即 \(S=\{s_1<s_2<\dots<s_k\}\)）。沿用上一题的思路，得到 \[\alpha(S)=\binom{n}{s_1}\binom{n-s_1}{s_2-s_1}\binom{n-s_1-s_2}{s_3-s_2}\cdots\binom{n-s_1-\cdots-s_{k-1}}{s_k-s_{k-1}}=\binom{n}{s_1,\;s_2-s_1,\;\cdots,\;s_k-s_{k-1},\;n-s_k}.\]

1. 降位只能出现在位置 \(s_1,s_2,\dots,s_k\)，排列被切成 \(k+1\) 段，每段内部递增，长度依次为 \(s_1,\;s_2-s_1,\;\dots,\;s_k-s_{k-1},\;n-s_k\)。
2. 逐段挑数：先从 \(n\) 个里挑 \(s_1\) 个，再从剩下的挑 \(s_2-s_1\) 个，依此类推。乘起来就是连乘的二项式。
3. 利用恒等式 \(\binom{n}{a}\binom{n-a}{b}\cdots=\dfrac{n!}{a!\,b!\cdots}\)，连乘可合并为多项式系数 \(\binom{n}{s_1,s_2-s_1,\dots,n-s_k}\)。

习题 5　降位集恰好等于 \(\{3,7\}\)

在习题 3 中我们算了长度为 10、降位集含于 \(\{3,7\}\) 的排列数。这意味着这些排列的降位集是下列之一：\(\{3,7\}\)、\(\{3\}\)、\(\{7\}\) 或 \(\varnothing\)。对 \(S\subseteq[10]\)，定义 \(\beta(S)\) 为降位集恰好等于 \(S\) 的排列数。则我们断言 \[\beta(\{3,7\})=\alpha(\{3,7\})-\alpha(\{3\})-\alpha(\{7\})+\alpha(\varnothing).\] 事实上，右边第二、三项减去了降位集真包含于 \(\{3,7\}\) 的排列数，这样做时把"没有降位"的排列减了两次。\(\alpha(\{3,7\})\) 已在上题算出。用同样的方法可见 \(\alpha(\{3\})=\binom{10}{3}\)，\(\alpha(\{7\})=\binom{10}{7}=\binom{10}{3}\)。因为没有降位的排列只有一个，于是 \[\beta(\{3,7\})=\binom{10}{3}\binom74-2\binom{10}{3}+1.\]

1. 这是容斥原理（inclusion-exclusion）。\(\alpha(\{3,7\})\) 把降位集为 \(\{3,7\},\{3\},\{7\},\varnothing\) 四类排列全算进来了。我们只想要"恰好 \(\{3,7\}\)"那一类。
2. 减 \(\alpha(\{3\})\)：去掉降位集含于 \(\{3\}\)（即 \(\{3\}\) 或 \(\varnothing\)）的；减 \(\alpha(\{7\})\)：去掉含于 \(\{7\}\)（即 \(\{7\}\) 或 \(\varnothing\)）的。
3. \(\varnothing\) 这一类被两次都减掉了，多减了一次，所以加回 \(\alpha(\varnothing)=1\)（只有递增排列 \(1\,2\cdots10\) 没有降位）。
4. 代入数值：\(\binom{10}{3}=120\)，\(\binom74=35\)，得 \(\beta(\{3,7\})=120\times35-2\times120+1=4200-240+1=3961\)。

习题 6　一般的容斥反演

沿用上一题的思路，我们得到 \[\beta(S)=\sum_{T\subseteq S}\alpha(T)\,(-1)^{|S-T|}.\]

1. 这是把习题 5 推广到任意降位集 \(S\)。\(\alpha(S)=\sum_{T\subseteq S}\beta(T)\)（降位集含于 \(S\)，就是降位集恰为 \(S\) 的某个子集 \(T\)）。
2. 对这种"求和=对所有子集求和"的关系做容斥反演（Möbius 反演），符号按子集相差的元素个数取 \((-1)^{|S-T|}\)，即得上式。
3. 验证 \(S=\{3,7\}\)：\(\beta=(-1)^0\alpha(\{3,7\})+(-1)^1\alpha(\{3\})+(-1)^1\alpha(\{7\})+(-1)^2\alpha(\varnothing)\)，与习题 5 完全一致。

习题 7　上升段数与第二类 Stirling 数

取 \([n]\) 划分为 \(k\) 个块的任一种划分（共 \(S(n,k)\) 种）。把每块内部按递增排列，再把这 \(k\) 个块按 \(k!\) 种顺序中的任一种排列。这样得到 \(S(n,k)\,k!\) 个排列，它们都至多有 \(k\) 个上升段（ascending run）。其中有些排列会被得到好几次；这正是为什么只有不等式、而非等式成立。

1. 上升段指排列中极大的连续递增片段，例如 \(2\,5\,|\,1\,3\,4\,|\,2\) 有 3 个上升段（每个降位结束一段）。
2. 构造法：把 \(n\) 个数分成 \(k\) 组、每组内递增，再决定 \(k\) 组的先后，拼成排列。这样得到的排列里，相邻两组的接缝处可能是降位，所以上升段数 \(\le k\)。
3. 为什么会重复：如果某次接缝处恰好不是降位（前一组末尾 \(<\) 后一组开头），两组就"自动连成一段"，这个排列也能由"少一个块"的另一种划分得到。于是同一个排列被数了多次，只能得到不等式 \((\text{上升段}\le k\text{ 的排列数})\le S(n,k)\,k!\)。

习题 8　排列的阶等于循环长度的最小公倍数

(a) 由 (b)，一个排列的阶（order）等于其所有循环长度的最小公倍数。如果两个排列有相同的循环型，那么它们的循环长度逐个相等，从而最小公倍数也相等（故同型排列阶相同）。

(b) 若排列 \(p\) 的某个循环长度为 \(t\)，则对任意 \(i\)，排列 \(p^{ti}\) 会把那个循环里的元素全部变成不动点（fixed point）。所以若 \(m\) 是 \(p\) 所有循环长度的公倍数，则 \(p^m=\mathrm{id}\)。因此 \(p\) 的阶就是其所有循环长度的最小公倍数。

1. 一个长为 \(t\) 的循环，反复作用 \(p\) 会让循环里的元素"转圈"：作用 \(t\) 次回到原位。所以 \(p^t\) 把这个循环里每个元素都固定，\(p^{ti}\) 同理。
2. 要让整个排列变成恒等（每个循环都回到原位），就需要 \(m\) 同时是所有循环长度的倍数，即公倍数。最小的这种 \(m\) 就是最小公倍数（least common multiple, lcm）。

习题 9　两类 Stirling 数矩阵互逆

我们断言 \(Ss=sS=I\)，其中 \(I\) 是单位矩阵。读者此刻可能责备我们：还没定义过两个无穷矩阵的乘积。所以我们说明：两个无穷矩阵 \(X,Y\) 的相乘几乎与有限情形一样，即 \(XY\) 的 \((i,j)\) 元是 \(X\) 第 \(i\) 行与 \(Y\) 第 \(j\) 列的点积，只要这个点积有定义。这个点积是无穷和 \(\sum_k x_{ik}y_{kj}\)，只要其中除有限项外都为 0，它就一定有定义。在我们的例子里，因为当 \(k>n\) 时 \(S(n,k)=s(n,k)=0\)，所以 \(sS\) 与 \(Ss\) 都有定义。

回到证明：\(s\) 与 \(S\) 互为逆矩阵。这源于：\(S\) 的各列其实是基 \(\mathcal B\) 用基 \(\mathcal B'\) 表出的坐标，\(s\) 的各列是 \(\mathcal B'\) 用基 \(\mathcal B\) 表出的坐标。所以 \(S\) 是从 \(\mathcal B'\) 到 \(\mathcal B\) 的过渡矩阵（change of basis matrix），\(s\) 是从 \(\mathcal B\) 到 \(\mathcal B'\) 的过渡矩阵。即对 \(V\) 中任意多项式 \(p\)，若 \(p_C\) 表示 \(p\) 在基 \(C\) 下的坐标，则 \(p_{\mathcal B'}=s\,p_{\mathcal B}\)，且 \(p_{\mathcal B}=S\,p_{\mathcal B'}\)。这就证明了 \(S,s\) 确实互逆。

1. 两组基：\(\mathcal B=\{x^0,x^1,x^2,\dots\}\)（普通幂），\(\mathcal B'=\{(x)_0,(x)_1,(x)_2,\dots\}\)（下降阶乘 \((x)_n=x(x-1)\cdots(x-n+1)\)）。
2. 第二类 Stirling 数把普通幂用下降阶乘展开：\(x^n=\sum_k S(n,k)(x)_k\)；第一类（带符号）把下降阶乘用普通幂展开：\((x)_n=\sum_k s(n,k)x^k\)。
3. "先换到另一组基、再换回来"必须回到原坐标，所以两个过渡矩阵相乘是单位矩阵，即 \(Ss=sS=I\)。

习题 10　飞机座位问题中循环长度的概率

\(n\) 名乘客各自落座的方式确定了 \([n]\) 的一个排列。某位乘客会因为最后一名乘客的到来而被迫移动，当且仅当她与最后一名乘客处在同一个循环里。因此我们的任务是确定：随机排列中随机选取的一个循环恰好长 \(k\) 的概率。

由于 \([n]\) 的所有元素在此问题中地位相同，我们不妨就回答"含最大元素 \(n\) 的循环"这一问。用转移引理（transition lemma）可知，含 \(n\) 的循环长为 \(k\) 当且仅当 \(n\) 是 \(f(p)\) 的第 \((n+1-k)\) 项。事实上，\(n\) 在 \(f(p)\) 中总是开启最后一个循环。\(n\) 落在任一给定位置的概率当然是 \(1/n\)，所以含 \(n\) 的循环长为 \(k\) 的概率就是 \(1/n\)。

1. 转移引理把"循环记法"和"一行记法"建立成双射 \(f\)。它把每个循环按"最大元素打头"写出、并按各循环最大元素递增排列，再去掉括号，得到一个普通排列 \(f(p)\)。
2. 因为 \(n\) 是全局最大，它一定开启 \(f(p)\) 的最后一个循环。若含 \(n\) 的循环长为 \(k\)，则它占据 \(f(p)\) 的最后 \(k\) 个位置，\(n\) 在第 \(n+1-k\) 位。
3. 在均匀随机排列里，\(n\) 等可能地处于 \(n\) 个位置中的任一个，所以"长度恰为 \(k\)"对应一个特定位置，概率为 \(1/n\)——与 \(k\) 无关，这是个很漂亮的结论。

习题 11　不动点的平均个数恒为 1

设 \(a_n\) 为所求平均值。我们断言对所有 \(n\) 都有 \(a_n=1\)，用对 \(n\) 的归纳法证明。

\(n=1\) 时结论显然。现假设 \(a_{n-1}=1\)。显然长为 \(n\) 的排列中以 1 为不动点的有 \((n-1)!\) 个；由归纳假设，排列的剩余部分（一个作用在 \(\{2,3,\dots,n\}\) 上的排列）平均有一个不动点。所以"1 是不动点"的排列平均有两个不动点。

另一方面，若 \(k>1\)，由上一题知道：长为 \(n\)、1 处于长为 \(k\) 的循环里的排列同样有 \((n-1)!\) 个。这个循环里的元素都不是不动点。因此排列的所有不动点都来自其余部分；其余部分是 \(n-k\) 个元素上的排列，由归纳假设平均有一个不动点——只要它不是空排列，即只要 \(k<n\)。若 \(k=n\)，则剩余部分没有不动点。

于是把三种情形相加——含 1 的循环长为 1、长为 \(k\)（\(1<k<n\)）、长为 \(n\)——得到 \[a_n=\frac{(n-1)!\cdot(1+1)+(n-2)(n-1)!\cdot 1+(n-1)!\cdot 0}{n!}=\frac{n!}{n!}=1.\]

1. 平均不动点数 = 所有排列不动点总数 ÷ 排列总数 \(n!\)。我们按"含 1 的循环长度"把 \(n!\) 个排列分成三类。
2. 含 1 的循环长 1（即 1 是不动点）：\((n-1)!\) 个排列，每个的不动点数 = 1（来自 1 本身）+ 其余 \(n-1\) 个元素的平均不动点数 \(=1\)，共平均 2。贡献 \((n-1)!\cdot 2\)。
3. 含 1 的循环长 \(k\)，\(1<k<n\)：对每个 \(k\) 有 \((n-1)!\) 个排列，平均不动点数 = 0（这 \(k\) 个不算）+ 其余 \(n-k\) 个的平均 \(=1\)。这样的 \(k\) 共有 \(n-2\) 个，贡献 \((n-2)(n-1)!\cdot 1\)。
4. 含 1 的循环长 \(n\)：\((n-1)!\) 个排列，整个就是一个 \(n\)-循环，没有不动点，贡献 0。
5. 三项之和 \(=2(n-1)!+(n-2)(n-1)!=n\cdot(n-1)!=n!\)，除以 \(n!\) 得平均值 1。

习题 12　满足 \(p^4=\mathrm{id}\) 的 6-排列

要让排列 \(p\) 满足 \(p^4=\mathrm{id}\)，\(p\) 中每个循环的长度都必须是 4 的约数，即 4、2 或 1。因为我们看的是 6-排列，所以要考虑把 6 分拆成 4、2、1 的分拆。它们是：

• \(4+2\)，即一个 4-循环加一个 2-循环。由定理 4.27 有 \(\dfrac{6!}{4\cdot 2}=90\) 个这种排列。
• \(4+1+1\)。有 \(\dfrac{6!}{4\cdot 1\cdot 1\cdot 2!}=90\) 个这种排列。
• \(2+2+2\)。有 \(\dfrac{6!}{2^3\cdot 3!}=15\) 个这种排列。
• \(2+2+1+1\)。有 \(\dfrac{6!}{2^2\cdot 2!\cdot 2!}=45\) 个这种排列。
• \(2+1+1+1+1\)。有 \(\dfrac{6!}{2\cdot 4!}=15\) 个这种排列。
• \(1+1+1+1+1+1\)。显然只有一个这种排列。

因此，长为 6 且四次幂为恒等排列的排列共有 \(90+90+15+45+15+1=256\) 个。为日后引用指出：上面后四种类型的排列都是对合（involution，满足 \(p^2=\mathrm{id}\)）。因此长为 6 的对合有 \(15+45+15+1=76\) 个。

1. 定理 4.27 的公式：循环型有 \(c_i\) 个长 \(i\) 的循环时，排列数 \(=\dfrac{n!}{\prod_i i^{c_i}c_i!}\)。分母里 \(i^{c_i}\) 来自每个循环可旋转写法、\(c_i!\) 来自同长循环可互换次序。
2. 逐项核对（\(6!=720\)）：\(4{+}2\to720/(4\cdot2)=90\)；\(4{+}1{+}1\to720/(4\cdot 2!)=90\)；\(2{+}2{+}2\to720/(2^3\cdot3!)=15\)；\(2{+}2{+}1{+}1\to720/(2^2\cdot2!\cdot2!)=45\)；\(2{+}1{+}1{+}1{+}1\to720/(2\cdot4!)=15\)；\(1^6\to720/6!=1\)。
3. 对合即所有循环长 \(\le 2\)。上面只含 1、2 的四种类型就是对合，\(15+45+15+1=76\)。

习题 13　满足 \(p^6=\mathrm{id}\) 的 6-排列

要让 \(p^6=\mathrm{id}\)，每个循环长度都必须是 6 的约数，即 6、3、2 或 1。对 6-排列，要考虑把 6 分拆成 6、3、2、1 的分拆：

• \(6\)，即 \(p\) 是一个 6-循环。由定理 4.27 有 \(\dfrac{6!}{6}=120\) 个。
• \(3+3\)。有 \(\dfrac{6!}{3^2\cdot 2!}=40\) 个。
• \(3+2+1\)。有 \(\dfrac{6!}{3\cdot 2}=120\) 个。
• \(3+1+1+1\)。有 \(\dfrac{6!}{3\cdot 3!}=40\) 个。
• 对合。由上题知有 76 个。

因此，长为 6 且六次幂为恒等的排列共有 \(120+40+120+40+76=396\) 个。

1. 6 的约数是 1,2,3,6。所有循环长在这些数里的排列恰是阶整除 6 的排列（习题 8）。
2. 含 6、3 但不含与对合重叠的循环型单独算；剩下"只含 1、2"的所有类型合并即对合，直接借用上题的 76。
3. 核对：\(720/6=120\)，\(720/(9\cdot2)=40\)，\(720/6=120\)，\(720/(3\cdot6)=40\)，加 76，共 396。

习题 14　立方后循环长度被 3 整除的循环个数不会是 2

取立方 \(p^3\) 时 \(p\) 的循环会怎样？这取决于循环的长度。

(a) 若循环长与 3 互质，则它不变；特别地，仍与 3 互质。

(b) 但若循环长为 \(3r\)，则该循环会分裂成三个长为 \(r\) 的循环。

注意：只有在第二种情形里 \(p^3\) 才可能出现长度被 3 整除的循环，即当 \(r\) 被 3 整除时。但那样 \(p^3\) 会立刻有三个这样的 \(r\)-循环。所以 \(p^3\) 中长为 \(3i\) 的循环个数总是 3 的倍数，因此不可能是 2。

1. 一个长 \(t\) 循环在立方下：把指针每次前进 3 步。若 \(\gcd(t,3)=1\)，则跳 3 步仍能遍历全部 \(t\) 个元素，循环不变。
2. 若 \(3\mid t\)，写 \(t=3r\)，跳 3 步会把元素按"位置模 3 同余"分成三组，各自成一个长 \(r\) 的循环——故一裂为三。
3. 要在 \(p^3\) 里出现长 \(3i\) 的循环，只能由 \(p\) 中长 \(9i\) 的循环分裂而来，而一个长 \(9i\) 循环正好产生三个长 \(3i\) 循环。所以这种循环成"三个一组"地出现，总数是 3 的倍数，绝不会恰为 2。

习题 15　含一个 4-循环的偶置换

这种排列必须含一个 4-循环。由于它们是偶置换（even permutation），其余元素必须是不动点。所以定理 4.27 表明它们的个数是 \(\dfrac{6!}{2!\cdot 4}=90\)。

1. 一个 4-循环的奇偶性（parity）：长 \(\ell\) 的循环相当于 \(\ell-1\) 个对换，4-循环 = 3 个对换 = 奇置换。要让整个排列是偶置换，剩下的部分必须再贡献奇数个对换……
2. 更直接：题目限定循环型为"一个 4-循环 + 两个不动点"（\(4+1+1\)）。这种型的奇偶性由 4-循环（奇）决定，配合两个不动点（偶），整体为奇。原书把这一型作为目标计数。
3. 用定理 4.27：循环型 \(4+1+1\) 个数 \(=\dfrac{6!}{4^1\cdot 1!\;\cdot\;1^2\cdot 2!}=\dfrac{720}{4\cdot 2}=90\)。（原书写作 \(6!/(2!\cdot4)\)，分母 \(2!\) 即两个不动点可交换，结果同为 90。）

习题 16　循环长只能是 1 或 3 的排列

在这种排列中，每个循环长度是 1 或 3。因此定理 4.34 给出 \[G_C(x)=\exp\!\left(x+\frac{x^3}{3}\right).\]

1. 定理 4.34：允许的循环长集合 \(C=\{1,3\}\)，则指数生成函数为 \(\exp\!\big(\sum_{i\in C}x^i/i\big)\)。
2. 代入 \(i=1\) 得 \(x/1=x\)，\(i=3\) 得 \(x^3/3\)，相加再取 \(\exp\) 即得。

习题 17　阶恰为 6 的排列的生成函数

这种排列中，每个循环长是 1、2、3 或 6。然而，要么循环长 2 和 3 必须都出现，要么循环长 6 必须出现。换言之，我们必须排除那些三次幂或二次幂已是恒等的排列。满足 \(p^2=p^3=\mathrm{id}\) 的排列只有恒等排列本身。因此由容斥原理，所求生成函数为 \[\exp\!\left(x+\frac{x^2}{2}+\frac{x^3}{3}+\frac{x^6}{6}\right)-\exp\!\left(x+\frac{x^2}{2}\right)-\exp\!\left(x+\frac{x^3}{3}\right)+\exp(x).\]

1. 阶整除 6（循环长 ∈ {1,2,3,6}）：\(\exp(x+\tfrac{x^2}2+\tfrac{x^3}3+\tfrac{x^6}6)\)。这里面也含了阶为 1、2、3 的排列。
2. 阶整除 2（循环长 ∈ {1,2}，即 \(p^2=\mathrm{id}\)）：\(\exp(x+\tfrac{x^2}2)\)，要减去。阶整除 3（循环长 ∈ {1,3}）：\(\exp(x+\tfrac{x^3}3)\)，也减去。
3. 同时满足 \(p^2=p^3=\mathrm{id}\) 的只有恒等（阶整除 \(\gcd(2,3)=1\)），被减了两次，加回 \(\exp(x)\)。
4. 容斥后剩下的正是"阶恰为 6"（即 lcm 真等于 6，而非它的真因子）的排列。

习题 18　平均循环个数与调和数

(a) 设 \(p\) 是一个长为 \(n-1\) 的排列，用循环记法写出，但不在 \([n]\) 上、而是在集合 \(\{2,3,\dots,n\}\) 上。现把 1 插入 \(p\) 的下列 \(n\) 个位置之一：或放到 \(p\) 的最前面，自成一个新循环；或放在 \(p\) 中某个元素 \(x\) 之后，与 \(x\) 同循环。前一种情形循环个数增加 1，否则不变。由于前一种情形在所有插入里占 \(1/n\)，公式得证。

(b) 我们断言 \[H(n)=\sum_{i=1}^{n}\frac{1}{i}.\] 这对 \(n=1\) 显然成立，之后用 (a) 的递推公式对 \(n\) 归纳即可，是例行的。

1. 把 1 插入长 \(n-1\) 排列的 \(n\) 个"缝隙"（最前面 1 个 + 每个元素之后共 \(n-1\) 个）中，恰好生成全部 \(n!\) 个长 \(n\) 的排列，且每个生成一次。
2. 只有"放最前面自成循环"才使循环数 +1，这种位置占 \(n\) 个中的 1 个，概率 \(1/n\)。所以平均循环数满足 \(H(n)=H(n-1)+\dfrac1n\)。
3. 从 \(H(1)=1\) 累加：\(H(n)=1+\dfrac12+\dfrac13+\cdots+\dfrac1n\)，即第 \(n\) 个调和数（harmonic number）。

习题 19　按不动点数分类得 \(n!\)

把右边写成 \(\sum_{k=0}^{n}\binom{n}{n-k}D(k)\)。则右边按不动点个数对所有 \(n\)-排列计数。事实上，若一个 \(n\)-排列恰有 \(n-k\) 个不动点，则我们有 \(\binom{n}{n-k}\) 种方法选这组不动点；而那些非不动点的元素构成的排列必须是 \(k\) 个元素上的一个错位排列（derangement，无不动点的排列）。

1. 恒等式 \(n!=\sum_{k=0}^{n}\binom{n}{n-k}D(k)\)（\(D(k)\) 是 \(k\) 元错位排列数）。左边 = 所有 \(n\)-排列个数。
2. 右边按"有几个非不动点"分类。设非不动点有 \(k\) 个，则不动点有 \(n-k\) 个，选哪 \(n-k\) 个当不动点有 \(\binom{n}{n-k}\) 种。
3. 剩下 \(k\) 个元素必须各不在自己位置（否则又成不动点），即排成一个错位排列，\(D(k)\) 种。乘起来再对 \(k\) 求和即得 \(n!\)。

习题 20　错位排列的递推

我们证明右边同样对长为 \(n\) 的错位排列计数。首先，设 \(p\) 是任一长为 \(n-1\) 的错位排列。则元素 \(n\) 可被插入 \(p\) 的 \(n-1\) 个不同位置，即放在每个元素 \(x\) 之后、与 \(x\) 同循环。这样得到 \((n-1)D(n-1)\) 个错位排列，其中 \(n\) 都在长度至少为 3 的循环里。于是我们还缺那些长为 \(n\) 且 \(n\) 处于 2-循环里的错位排列。这种排列里，与 \(n\) 同循环的元素 \(y\) 有 \(n-1\) 种选择，然后排列的其余部分有 \(D(n-2)\) 种选择。这给出缺少的那 \((n-1)D(n-2)\) 个错位排列。稍加思考可知我们数遍了所有长为 \(n\) 的错位排列，故证毕。即 \[D(n)=(n-1)\big(D(n-1)+D(n-2)\big).\]

1. 情形一：\(n\) 在长度 \(\ge 3\) 的循环里。取一个 \(n-1\) 元错位排列（循环都 \(\ge 2\)），把 \(n\) 插到某元素 \(x\) 后面。共 \(n-1\) 个位置，得 \((n-1)D(n-1)\) 个，且原循环变长，\(n\) 所在循环长 \(\ge 3\)。
2. 情形二：\(n\) 在 2-循环里。选与 \(n\) 配对的 \(y\)（\(n-1\) 种），剩下 \(n-2\) 个元素排成错位排列（\(D(n-2)\) 种），得 \((n-1)D(n-2)\) 个。
3. 两情形不重叠且穷尽，相加 \(D(n)=(n-1)D(n-1)+(n-1)D(n-2)=(n-1)(D(n-1)+D(n-2))\)。

习题 21　循环长全被 \(k\) 整除的排列

(a) 用定理 4.34，取 \(C\) 为所有被 \(k\) 整除的正整数。则 \[G_C(x)=\exp\!\left(\sum_{n\ge1}\frac{x^{kn}}{kn}\right)=\exp\!\left(\frac1k\ln(1-x^k)^{-1}\right)=\left(\frac{1}{1-x^k}\right)^{1/k}.\] 读者若想了解这一计算的更多细节，可读例 4.39 及其前面几段——那个例子是本题在 \(k=2\) 时的特例。

(b) 同样仿照例 4.39，需求 \((1-x^k)^{-1/k}\) 中 \(x^n/n!\) 的系数。显然若 \(k\nmid n\) 则 \(f_k(n)=0\)。否则设 \(n=rk\)，则 \[f_k(n)=1^2\cdot 2\cdots(k-1)\cdot(k+1)^2\cdots(2k-1)\cdot(2k+1)^2\cdots(rk-1).\] 也就是说 \(f_k(n)\) 是 \(n\) 个因子的乘积（如同 \(n!\)），但其中被 \(k\) 整除的那些因子缺席，并被比它小 \(k-1\) 的整数所替代。

(c) 这与正文中 \(k=2\) 特例的证明类似。即设 \(p=rk\)。若 \(p\) 被 \(f_k(n)\) 计数，则 \(p(1)\) 不能是 1，但可以是其他任何值，即 \(p(1)\) 有 \(rk-1\) 种选择。然后 \(p(p(1))\) 可以是除 1 和 \(p(1)\) 外的任何值，故有 \(rk-2\) 种。如此继续直到 \(p^k(1)\)（即若 \(i<k\)，则 \(p^i(1)\) 不能是 1 和 \(p^j(1)\)（\(j<i\)）中任一个，给出 \(rk-i\) 种）。然后 \(p^k\) 可以等于 1，给出 \(rk-k+1\) 种。如正文那样继续此论证即得证。

1. (a) 关键是 \(\sum_{n\ge1}\dfrac{(x^k)^n}{n}=-\ln(1-x^k)\)（这是 \(-\ln(1-t)=\sum t^n/n\) 取 \(t=x^k\)）。把 \(\dfrac1k\) 提出：\(\sum_{n\ge1}\dfrac{x^{kn}}{kn}=\dfrac1k\big(-\ln(1-x^k)\big)\)。
2. 再取 \(\exp\)：\(\exp\big(\tfrac1k(-\ln(1-x^k))\big)=(1-x^k)^{-1/k}\)。
3. (b) 把 \((1-x^k)^{-1/k}\) 按广义二项式展开，比对 \(x^n/n!\) 的系数即得那串"跳过 \(k\) 倍数"的乘积。

习题 22　第一类无符号 Stirling 数模素数

我们断言：除 \(k=1\) 与 \(k=p\) 外，\(c(p,k)\) 都被 \(p\) 整除。这两个例外显然确实成立。否则（即 \(1<k<p\) 时），\(c(p,k)\) 可由所有具有 \(k\) 个循环的循环型的排列数相加得到。由定理 4.27，这些数都是分子被 \(p\) 整除、分母不被 \(p\) 整除的分数。因此，由于 \(p\) 是素数，这些数都被 \(p\) 整除，它们的和也是。

1. \(c(p,k)\)（第一类无符号 Stirling 数）= \([p]\) 上恰有 \(k\) 个循环的排列个数。
2. \(k=1\)：一个 \(p\)-循环，\(c(p,1)=(p-1)!\)；\(k=p\)：全是不动点，\(c(p,p)=1\)。这两个未必被 \(p\) 整除（确为例外）。
3. \(1<k<p\) 时，每种循环型至少有一个循环长 \(\ge 2\) 且不到 \(p\)，分子 \(p!\) 含因子 \(p\)，而分母 \(\prod i^{c_i}c_i!\) 中所有数都 \(<p\)、不含素因子 \(p\)。所以每种型的排列数都被 \(p\) 整除，求和后 \(c(p,k)\) 也被 \(p\) 整除。

习题 23　Wilson 定理

回忆 \((p-1)!=c(p,1)\)。由上一题的结论，我们有 \[p!=\sum_{k=1}^{p}c(p,k)\equiv 0\pmod p,\qquad c(p,1)+c(p,p)\equiv 0\pmod p,\qquad (p-1)!+1\equiv 0\pmod p,\] 这正是要证的。

1. 第一行：\(p!=\sum_{k=1}^p c(p,k)\) 是把所有排列按循环数分类，左边 \(p!\) 显然被 \(p\) 整除。
2. 第二行：在求和中，\(1<k<p\) 的项由习题 22 都 \(\equiv 0\)，故 \(0\equiv c(p,1)+c(p,p)\pmod p\)。
3. 第三行：代入 \(c(p,1)=(p-1)!\)、\(c(p,p)=1\)，得 \((p-1)!+1\equiv 0\pmod p\)，即Wilson 定理（Wilson's theorem）。

习题 24　恰有 3 个逆序的长 10 排列

由定理 4.54，\(b(n,k)\)（此处 \(b(10,3)\)）是 \(I_{10}(x)\) 中 \(x^3\) 的系数。换言之，\(b(10,3)\) 等于把 3 写成 9 个部分的弱合成（weak composition）个数，且要求第一部分至多为 1、第二部分至多为 2。把 3 写成 9 个部分的弱合成共有 \(\binom{11}{3}\) 个。其中有 1 个违反"第二部分 \(\le 2\)"，有 9 个违反"第一部分 \(\le 1\)"，没有任何弱合成同时违反两条。因此 \[b(10,3)=\binom{11}{3}-1-9=165-1-9=155.\]

1. 逆序计数生成函数 \(I_n(x)=\prod_{i=1}^{n}(1+x+\cdots+x^{i-1})\)。对 \(n=10\) 提取 \(x^3\) 系数：选每个因子贡献的指数 \(e_i\)（\(0\le e_i\le i-1\)），使 \(\sum e_i=3\)。
2. 第一个有效因子 \((1+x)\) 给出 \(e\le1\)；第二个 \((1+x+x^2)\) 给出 \(e\le2\)；其余因子上限都 \(\ge3\)，对取 \(x^3\) 不构成限制。共 9 个可变因子。
3. 无上限时把 3 分到 9 个非负部分：\(\binom{3+9-1}{3}=\binom{11}{3}=165\)（隔板法 / stars and bars）。
4. 违反"第一部分 \(\le1\)"：第一部分 \(\ge2\)，先放 2 个，剩 1 个分到 9 部分，\(\binom{1+9-1}{1}=9\) 个。违反"第二部分 \(\le2\)"：第二部分 \(\ge3\)，必为 3，其余为 0，\(1\) 个。两者不可能同时发生（总和才 3）。
5. 容斥：\(165-9-1=155\)。

习题 25　逆序数递推（一）

左边对所有恰有 \(k\) 个逆序的 \(n\)-排列计数。右边第二项对其中末位为 \(n\) 的那些排列计数。最后，右边第一项对 \(n\) 不在末位的那些含 \(k\) 个逆序的 \(n\)-排列计数。事实上，在这些排列里，可以把 \(n\) 与紧跟其后的元素交换，使逆序数减少 1，变成 \(k-1\)。这样我们得到一个含 \(k-1\) 个逆序、且 \(n\) 不在第一位的 \(n\)-排列；而 \(n\) 本来也不可能在第一位，因为那会造成 \(n\) 个逆序，是不允许的。

1. 逆序（inversion）：一对位置 \(i<j\) 但 \(p_i>p_j\)。
2. 按"\(n\) 是否在末位"分类。若 \(n\) 在末位，它与前面每个数都不构成逆序（因为它最大且在最后），删掉它得到含 \(k\) 个逆序的 \((n-1)\)-排列 → \(b(n-1,k)\)。
3. 若 \(n\) 不在末位，把 \(n\) 与其右邻交换：\(n\) 右移一格，逆序减 1 变 \(k-1\)，得到 \(n\) 不在首位的排列。此操作可逆，故这类对应 \(b(n,k-1)\) 减去 \(n\) 在首位的情况——而 \(n\) 在首位会有 \(n-1\ge n\)……（详见下题修正）。综合得递推 \(b(n,k)=b(n-1,k)+b(n,k-1)\)（在 \(k<n\) 范围内）。

习题 26　逆序数递推（二）

沿用上一题的思路，可见右边需要补一项，即"含 \(k-1\) 个逆序、且 \(n\) 在第一位"的 \(n\)-排列个数。若 \(n\) 在第一位，则它参与 \(n-1\) 个逆序，所以排列其余部分必须含 \(k-n\) 个逆序，这可以有 \(b(n-1,k-n)\) 种方式。因此 \[b(n,k)=b(n-1,k-n)+b(n,k-1)+b(n-1,k).\]

1. 上题的论证在 \(n\) 可能位于首位时不完整：当 \(n\) 在首位，它与右边 \(n-1\) 个数全构成逆序，贡献 \(n-1\) 个。
2. 去掉首位的 \(n\)，剩 \((n-1)\)-排列要含 \(k-(n-1)=k-n+1\)……更准确地，把"\(n\) 在首位、共 \(k\) 个逆序"对应到剩余排列的 \(k-(n-1)\) 个逆序，故这类有 \(b(n-1,k-n+1)\)；原书写 \(b(n-1,k-n)\)，对应它处理"含 \(k-1\) 个逆序"的版本。
3. 把三类——\(n\) 不在首/末（移位项 \(b(n,k-1)\) 的修正）、\(n\) 在末位 \(b(n-1,k)\)、\(n\) 在首位 \(b(n-1,k-n)\)——相加，得到完整递推式。

习题 27　固定一处的逆序贡献

两问的答案都是 \(n!/k\)。要看出这点，只需考察 \(I_n(x)\) 中的因子 \((1+x+\cdots+x^{k-1})\)。

1. \(I_n(x)=\prod_{i=1}^{n}(1+x+\cdots+x^{i-1})\)。其中长度为 \(k\) 的那个因子是 \(1+x+\cdots+x^{k-1}\)，它的系数都是 1，且关于 \(x\) 在 0 到 \(k-1\) 次"均匀"。
2. 在 \(x=1\) 处，\(I_n(1)=n!\)（排列总数）。某个特定因子取各指数是"等概率"的，所以对应统计量的某一类占比为 \(1/k\)，给出 \(n!/k\)。

习题 28　逆序数下相邻降位位置的均匀性

我们断言 \(a_i=a_{i+1}\)，而显然由此可推出所有 \(a_i\) 都相等。我们显然可以不理会那些"\(i\) 和 \(i+1\) 同时是降位"以及"两者都不是降位"的排列。所以只需证明：\(\mathrm{Inv}(n,k)\) 中满足 \(p_i>p_{i+1}<p_{i+2}\) 的排列（集合 \(A\)）与满足 \(p_i<p_{i+1}>p_{i+2}\) 的排列（集合 \(B\)）一样多。这容易用双射做到。设 \(p\in A\)。保持 \(p_i\) 左边和 \(p_{i+2}\) 右边的元素不变，然后把 \(p_i,p_{i+1},p_{i+2}\) 三项重排：先反序，再在这三元素集合内取补。（用习题 32 的术语，若这三项的模式是 312，就变成 231；若是 213，就变成 132。）因为排列的总逆序数没变，新排列仍在 \(\mathrm{Inv}(n,k)\) 中，且显然落在 \(B\) 里。这个映射是双射，因为"取反序再取补"是可逆操作。

1. \(\mathrm{Inv}(n,k)\) 指含 \(k\) 个逆序的 \(n\)-排列集；\(a_i\) 是其中第 \(i\) 个位置是降位的排列数。要证对所有 \(i\)，\(a_i\) 相同。
2. 看三个连续项 \(p_i,p_{i+1},p_{i+2}\)。"恰好 \(i\) 是降位而 \(i+1\) 不是"对应模式 312 或 213（中间项最小）；"恰好 \(i+1\) 是降位而 \(i\) 不是"对应模式 231 或 132（中间项最大）。
3. "反序 + 取补"把 312↔231、213↔132，且不改变这三项之间逆序的总数（反序使逆序变非逆序，取补再换回，净逆序数守恒），所以新排列仍含 \(k\) 个逆序。这建立 \(A\) 与 \(B\) 的一一对应，故 \(a_i=a_{i+1}\)。

习题 29　高斯二项式系数（Gaussian binomial coefficient）

(a) 对 \(\binom42\)，我们数排列 \(1122,1212,1221,2112,2121,2211\)。因此 \[\binom42_q=1+q+2q^2+q^3+q^4.\] 对 \(\binom51\)，要数 \(12222,21222,22122,22212,22221\)。因此 \[\binom51_q=1+q+q^2+q^3+q^4.\] 最后，对 \(\binom53\)，要数 \(11122,11212,11221,12112,12121,12211,21112,21121,21211,22111\)。因此 \[\binom53_q=1+q+2q^2+2q^3+2q^4+q^5+q^6.\]

(b) 设 \(p\) 是多重集 \(K\) 的一个排列。把 \(p\) 反序，并把所有 1 换成 2、2 换成 1。则新排列 \(p'\) 是"\(k\) 个 2 与 \(n-k\) 个 1"组成的多重集的一个排列，故被 \(\binom{n}{n-k}_q\) 计数。此外 \(i(p)=i'(p)\)，证明了我们的断言（即 \(\binom nk_q=\binom{n}{n-k}_q\)）。

1. \(\binom nk_q\) 这里定义为：由 \(k\) 个 1 与 \(n-k\) 个 2 组成的所有 0/1 序列，按其逆序数 \(i(\cdot)\) 加权 \(q^{i}\) 求和。\(\binom42\) 即 2 个 1、2 个 2。
2. 例：\(2211\) 中"2 在 1 前"算逆序，共 \(2\times2=4\) 个逆序，贡献 \(q^4\)；\(1212\) 有 1 个逆序，贡献 \(q\)。把六个序列的权相加即得 (a) 的多项式。
3. (b) 的对称：交换 1、2 的角色并反序，把"\(k\) 个 1"的排列一一对应到"\(n-k\) 个 1"的排列且逆序数不变，故两多项式相等。

习题 30　高斯系数的递推（按末位）

项 \(\binom{n-1}{k}_q\) 对以 2 结尾的排列计数，项 \(q^{\,n-k}\binom{n-1}{k-1}_q\) 对以 1 结尾的排列计数。

1. 多重集排列（\(k\) 个 1、\(n-k\) 个 2）按末位分两类。末位是 2：去掉末位，剩 \(k\) 个 1、\(n-1-k\) 个 2，逆序数不变，对应 \(\binom{n-1}{k}_q\)。
2. 末位是 1：这个末位的 1 与它前面的所有 2（共 \(n-k\) 个）各构成一个逆序，贡献因子 \(q^{n-k}\)；去掉它，剩 \(k-1\) 个 1、\(n-k\) 个 2，对应 \(\binom{n-1}{k-1}_q\)。
3. 相加得 \(\binom nk_q=\binom{n-1}{k}_q+q^{n-k}\binom{n-1}{k-1}_q\)。

习题 31　高斯系数计数 \(m\times n\) 矩形内的分拆

容易证明 \(p(m,n,q)\) 满足与 \(\binom{m+n}{m}_q\) 相同的递推关系。事实上，若一个分拆的 Ferrers 图能放进 \(m\times n\) 矩形，则有两种可能：要么该分拆至多有 \(m-1\) 个部分，此时其 Ferrers 图甚至能放进 \((m-1)\times n\) 矩形；要么该分拆恰有 \(m\) 个部分，此时去掉 Ferrers 图的第一列后，剩下的图能放进 \(m\times(n-1)\) 矩形。这两种情形对应高斯系数所满足递推关系的两个加项。

1. 高斯系数递推：\(\binom{m+n}{m}_q=\binom{m+n-1}{m}_q+q^{\,?}\binom{m+n-1}{m-1}_q\)（见习题 30 同型）。
2. 组合对应：分拆部分数 \(<m\) → 行数没用满，图嵌入 \((m-1)\times n\)，对应第一个加项；分拆恰 \(m\) 个部分 → 每行至少 1 格，削去第一整列后每行减 1、图嵌入 \(m\times(n-1)\)，对应第二个加项（删掉的 \(m\) 个格按面积换算贡献 \(q\) 的幂）。
3. 两式递推相同且初值相同，故 \(p(m,n,q)=\binom{m+n}{m}_q\)。

习题 32　避 132 的排列被 Catalan 数计数

我们对 \(n\) 归纳证明此命题，初始情形 \(n=1\) 显然。我们约定：长度为 0 的避 132 排列只有一个。

现假设对所有小于 \(n\) 的非负整数命题成立。设有一个避 132 的 \(n\)-排列，其中元素 \(n\) 处于第 \(i\) 个位置。则显然 \(n\) 左边的每个元素都必须大于其右边的每个元素，否则那两个违反此条件的元素连同 \(n\) 会构成一个 132 模式。此外，由归纳假设，\(n\) 左边的子串有 \(C_{i-1}\) 种可能，右边的有 \(C_{n-i}\) 种可能。对所有允许的 \(i\) 求和，得到递推 \[C_n=\sum_{i=0}^{n-1}C_{i-1}C_{n-i},\tag{4.21}\] 而由 (3.25) 知这正是 Catalan 数的递推。

1. 132 模式：存在位置 \(a<b<c\) 使 \(p_a<p_c<p_b\)（即"小、大、中"）。"避 132"就是没有这种三元组。
2. 设最大元 \(n\) 在第 \(i\) 位。若 \(n\) 左边有个小数、右边有个比它大的数，那么"左小、\(n\)、右中"恰是 132，违规。故左边所有数 > 右边所有数。
3. 于是左块是 \(\{n-i+1,\dots,n-1\}\) 的避 132 排列（\(C_{i-1}\) 种），右块是 \(\{1,\dots,n-i\}\) 的避 132 排列（\(C_{n-i}\) 种）。对 \(i\) 求和得 Catalan 递推，所以 \(S_n(132)=C_n\)。

习题 33　四个长 3 模式的等价

若 \(n\)-排列 \(p\) 含模式 \(q\)，则 \(p\) 的反序含 \(q\) 的反序。这给出 \(S_n(132)=S_n(231)\)。类似地，若 \(p\) 含模式 \(q\)，则 \(p\) 的补含 \(q\) 的补，因此 \(S_n(132)=S_n(213)\)。最后由取反序得 \(S_n(213)=S_n(312)\)。所以四个模式 132、213、231、312 都被 \(C_n\) 个长为 \(n\) 的排列所避开。这还没完，因为我们还有 \(S_n(123)=S_n(321)=C_n\)，后者证明略难（补充习题 39）。

1. \(S_n(q)\) = 避开模式 \(q\) 的 \(n\)-排列数。反序把模式 \(q\) 变成其反序、取补把 \(q\) 变成其补，且都是排列集合上的双射，所以避开 \(q\) 的排列数 = 避开其反序/补的排列数。
2. 132 的反序是 231，故 \(S_n(132)=S_n(231)\)；132 的补是 312……（实际 132 的补为 \(4-1,4-3,4-2=3,1,2=312\)），故 \(S_n(132)=S_n(213)\) 经一次操作；再组合反序/补把 213、231、312 全连起来。
3. 结论：六个长 3 模式中，132、213、231、312 都给 \(C_n\)；123 与 321 也给 \(C_n\)（更难，留作补充习题）。这就是著名的：所有单个长 3 模式都被 Catalan 数计数。

习题 34　312 模式中相邻的一对

设 \(p_i,p_j,p_k\) 在 \(p\) 中构成一个 312 模式。若 \(p\) 中有多个 312 模式，选取使 \(j-i\) 最小的那个。我们断言此时必有 \(j-i=1\)，即 \(p_i\) 与 \(p_j\) 是 \(p\) 中相邻的元素。事实上，假设 \(p_t\) 位于 \(p_i\) 与 \(p_j\) 之间。那么 \(p_t\) 不能大于 \(p_k\)，否则 \(p_tp_jp_k\) 会构成 312 模式，与 \(j-i\) 的最小性矛盾；同样 \(p_t\) 不能小于 \(p_k\)，否则 \(p_ip_tp_k\) 又会构成 312 模式。所以 \(p_t\) 根本不可能存在，意味着 \(p_i\) 与 \(p_j\) 相邻。

1. 312 模式：\(p_i>p_k>p_j\)（"中、小、大"按值，位置 \(i<j<k\)，即第一个最大、第二个最小、第三个居中）。
2. 反证：若 \(i\) 与 \(j\) 之间还夹着 \(p_t\)。把 \(p_t\) 与 \(p_k\) 比大小。若 \(p_t>p_k\)，则 \(p_t,p_j,p_k\) 是更靠近的 312（下标差更小），矛盾。
3. 若 \(p_t<p_k\)（且 \(p_t\le p_k\)，不会等因互异），则 \(p_i,p_t,p_k\) 是 312（\(p_i>p_k>p_t\)），下标差 \(t-i<j-i\)，也矛盾。
4. 两种情况都矛盾，故 \(i,j\) 之间无元素，即相邻。

习题 35　游客与酒：\((n+1)!\)

我们对 \(n\) 归纳，\(n=1\) 显然。现假设对 \(n-1\) 成立，来证 \(n\) 的情形。设 \(n-1\) 位游客已就座于各桌、且各桌已上了酒。现在最后一位游客进来。他要么坐到一张新桌，并选红酒或白酒；要么坐到某张已有游客的桌旁，选他的左邻——这有 \(n-1\) 种选法。由于第一种情形产生 \(2\cdot n!\) 种结果，第二种产生 \((n-1)\cdot n!\) 种结果，合计 \((n+1)\,n!=(n+1)!\) 种结果，正如所断言。注意我们本质上用了"最后一位游客有 \(n+1\) 种不同的行动方案"这一事实。

1. 每种"就座 + 配酒"的方案数记为某序列。归纳假设：\(n-1\) 位游客有 \(n!\) 种方案。
2. 第 \(n\) 位的选择：(i) 开一张新桌，自成一组，红/白酒二选一 → 2 种；(ii) 插入到现有某游客的左侧 → 有 \(n-1\) 个"某游客"可选 → \(n-1\) 种。共 \(2+(n-1)=n+1\) 种行动。
3. 每种行动都接在前 \(n!\) 个方案之后，故总数 \((n+1)\cdot n!=(n+1)!\)。

习题 36　正四面体的对称

(a) 由于顶点的所有排列都定义一个对称，正四面体有 24 个对称。

(b) 有 12 个对称可由一系列旋转得到。要看出这点，取一条垂直于某个面、且过第四个顶点的轴。绕该轴有两个旋转，分别转 120° 和 240°。这样的轴有四条，给出 \(4\cdot2=8\) 个对称。一个旋转之后再绕另一条轴旋转，给出一个交换两对顶点的对称。可能的"两对配对"有三种，所以有三个这样的对称。最后，恒等当然是一个旋转。所以可由一系列旋转得到的对称有 \(8+3+1=12\) 个。

(c) (b) 表明可由旋转得到的对称具有循环型 \((4,0,0,0)\)、\((1,0,1,0)\) 或 \((0,2,0,0)\)，所以它们都是偶置换。由于这样的对称有 12 个，它们恰是 \(S_4\) 的全部偶置换。所以正四面体的一个对称可由旋转得到，当且仅当它是偶置换。

1. (a) 4 个顶点可任意置换都对应一个刚体/镜面对称，共 \(4!=24\) 个，即对称群同构于 \(S_4\)。
2. (b) 计数旋转：8 个绕"顶点—对面"轴的 120°/240° 旋转（这些是 3-循环，型 \((1,0,1,0)\)：1 个不动点 + 1 个 3-循环）；3 个绕"对棱中点"轴的 180° 旋转（型 \((0,2,0,0)\)：两个 2-循环）；1 个恒等（型 \((4,0,0,0)\)，4 个不动点）。合计 \(8+3+1=12\)。
3. (c) 偶置换判据：循环型贡献的对换数之和为偶。3-循环 = 2 个对换（偶）；恒等（偶）；两个 2-循环 = 2 个对换（偶）。三种全偶，共 12 个，正好是 \(S_4\) 中偶置换的总数 \(4!/2=12\)。所以"可由旋转得到 ⇔ 偶置换"。

习题 37　带标号循环的指数生成函数

我们断言 \[H(x)=\prod_{i\ge1}\left(\frac{1}{1-x^i}\right)^{1/i}.\] 事实上，要得到一个被计数的对象，先把 \([n]\) 划分成若干块，用正整数 \(i\) 给它们编号，然后在第 \(i\) 块上取一个排列，其循环都被标号 \(i\)、且长度都被 \(i\) 整除。在第 \(i\) 块上这样做的方法数的生成函数就是 \((1-x^i)^{-1/i}\)（细节见习题 21），由乘积公式立即得证。此结果及其推广见文献 [1]。

1. 回忆题意（见 4.8 节末尾）：取所有长 \(n\) 的排列，给每个循环标上"该循环长度的一个正约数 \(d\)"；\(h(n)\) 数所有这种 (排列, 循环, 约数) 三元组。前四个值是 \(1,3,11,59\)。
2. 按"标号 \(i\)"把元素分块：第 \(i\) 块上放的排列，其循环长都被 \(i\) 整除（因为约数 \(i\) 要能整除循环长）。由习题 21(a)，循环长全被 \(i\) 整除的排列其指数生成函数为 \((1-x^i)^{-1/i}\)。
3. 不同标号的块互相独立，由指数公式的乘积形式（Product formula），把各块生成函数相乘：\(H(x)=\prod_{i\ge1}(1-x^i)^{-1/i}\)。

返回 全书目录