2.9　习题解答Solutions to exercises

本节速览这是第 2 章配套习题（共 37 题）的解答。题目主要围绕：排列与函数计数（单射、满射、单调函数）、合成（composition）与弱合成、整数分拆（partition）与 Ferrers 图、球放盒模型，以及容斥原理（inclusion–exclusion）。下面逐题给出译文，再用分步推演讲清每一步“为什么”。

为方便阅读，先约定几个贯穿全节的记号：\([n]=\{1,2,\dots,n\}\)；下降阶乘 \((k)_n=k(k-1)\cdots(k-n+1)\)（即从 \([n]\) 到 \([k]\) 的单射个数）；第二类 Stirling 数 \(S(n,k)\)（把 \(n\) 元集划分成 \(k\) 个非空块的方法数）；Bell 数 \(B(n)\)（\([n]\) 的全部划分数）；错位排列数 \(D(i)\)（\([i]\) 上没有不动点的排列数）。

---

第 1 题　双射、单射、满射的球放盒模型

(a) 这样的函数 \(f\) 称为双射（bijection）。事实上，\(f\) 是满射（surjective）保证了每个 \(t\in T\) 在 \(f\) 下至少有一个原像；\(f\) 是单射（injective）保证了每个 \(t\in T\) 在 \(f\) 下至多有一个原像。

(b) 可把 \([n]\) 的元素看成可区分的球，把 \([k]\) 的元素看成可区分的盒子。于是由习题 2.52(c)，答案是 \((k)_n\)。

(c) 用与 (b) 相同的模型，由习题 2.52(b)，答案是 \(S(n,k)\,k!\)。

1. (a) 为什么“既单又满”就是双射。满射说“每个目标至少被命中一次”，单射说“每个目标至多被命中一次”。两句话合起来就是“恰好一次”，这正是双射的定义——\(f\) 把 \([n]\) 与 \(T\) 的元素一一配对。
2. (b) 单射 = 把球放进不同盒子。一个从 \([n]\)（球）到 \([k]\)（盒）的单射，等价于让每个球进一个盒、且没有两个球同盒。第 1 号球有 \(k\) 个盒可选，第 2 号球要避开已占的盒、有 \(k-1\) 个，……第 \(n\) 号球有 \(k-n+1\) 个。由乘法原理得 \[k(k-1)\cdots(k-n+1)=(k)_n.\]
3. (c) 满射 = 每个盒非空。从 \([n]\) 到 \([k]\) 的满射要求每个盒至少一个球。先把 \(n\) 个球分成 \(k\) 个非空的“无标号堆”，方法数是 \(S(n,k)\)；再给这 \(k\) 个堆贴上 \(k\) 个不同盒子的标签，方法数是 \(k!\)。乘起来 \(S(n,k)\,k!\)。

第 2 题　令 \(b_i=a_i+i-1\)

令 \(b_i=a_i+i-1\)。其余细节留给读者填写。

1. 该题要在“\(n\) 的、恰 \(k\) 个（可相等）部分的普通分拆”与“\(n+\binom{k}{2}\) 的、恰 \(k\) 个相异部分的分拆”之间建立一一对应。
2. 把普通分拆的部分按递增排列：\(a_1\le a_2\le\dots\le a_k\)（各 \(\ge 1\)）。令 \(b_i=a_i+(i-1)\)，即加上阶梯 \(0,1,2,\dots,k-1\)。则 \[b_{i+1}-b_i=(a_{i+1}-a_i)+1\ge 1,\] 故 \(b_1相异部分。注意：必须按递增下标给部分加阶梯，才能把“可相等”撑开成“严格递增”。
3. 加上的阶梯总和为 \(0+1+\dots+(k-1)=\binom{k}{2}\)，所以总和从 \(n\) 变成 \(n+\binom{k}{2}\)。反过来，给定相异分拆 \(b_1<\dots

第 3 题　\(n\) 的合成共有 \(2^{n-1}\) 个

(a) 断言这个数是 \(2^{n-1}\)。事实上，把第 1 章习题 13 的结论中的 \(n\) 换成 \(n-1\) 即得。

(b) 当 \(n=1\) 时命题成立。现假设对 \(n-1\) 成立，往证对 \(n\) 成立。我们构造一个从 \(n\) 的全体合成之集 \(C(n)\) 到 \(n-1\) 的全体合成之集 \(C(n-1)\) 的2 对 1 映射 \(f\)，定义如下：设 \(c=(c_1,c_2,\dots,c_k)\in C(n)\)，令 \[f(c)=\begin{cases}(c_1-1,\,c_2,\dots,c_k)& \text{若 }c_1>1,\\[2pt](c_2,\dots,c_k)& \text{若 }c_1=1.\end{cases}\] 容易看出 \(f\) 确为 2 对 1：\(C(n-1)\) 中每个元素 \(d\) 在 \(f\) 下都有两个原像——一个由把 \(d\) 的首项加 1 得到，另一个由在 \(d\) 前面添一个 1 得到。读者可自行验证，这样得到的 \(n\) 的 \(2^{n-1}\) 个合成确实两两不同。

1. 什么是合成。\(n\) 的一个合成（composition）是把 \(n\) 写成若干有序正整数之和，例如 \(3=3=2{+}1=1{+}2=1{+}1{+}1\)，共 4 个，恰为 \(2^{3-1}=4\)。
2. 2 对 1 为何给出 \(2^{n-1}\)。“2 对 1”意味着定义域恰好是值域的 2 倍大：\(|C(n)|=2\,|C(n-1)|\)。配合归纳假设 \(|C(n-1)|=2^{(n-1)-1}=2^{n-2}\)，得 \(|C(n)|=2\cdot 2^{n-2}=2^{n-1}\)。
3. 逐项验证每个 \(d\) 恰有两原像。给定 \(d=(d_1,\dots)\in C(n-1)\)：把首项 \(+1\) 得 \((d_1+1,d_2,\dots)\)，其首项 \(>1\)，落入 \(f\) 的第一支且映回 \(d\)；在前面添 1 得 \((1,d_1,\dots)\)，首项 \(=1\)，落入第二支且映回 \(d\)。这两个原像首项一大于 1、一等于 1，必然不同，所以恰好两个。

第 4 题　不限部分数时弱合成有无穷多个

若不指定部分的个数，则 \(n\) 的弱合成（weak composition，允许部分为 0）有无穷多个。事实上，我们可以在任何一个 \(n\) 的弱合成末尾任意添加许多个 0。

1. 弱合成允许 \(0\) 作为部分。例如 \(n=2\) 可写成 \((2),(2,0),(2,0,0),(2,0,0,0),\dots\)，每个都是合法弱合成且互不相同。
2. 这样的写法可以无限延长，故弱合成的个数无界。这正说明：谈“弱合成的个数”时，必须先固定部分数 \(k\)，否则答案是无穷。固定 \(k\) 后，\(n\) 的 \(k\) 部分弱合成个数才有限，为 \(\binom{n+k-1}{k-1}\)（见第 6、7、8 题）。

第 5 题　兄弟姐妹成对的分组

由于成对的兄弟姐妹不能被拆开，我们把每一对看作一个“超级孩子”。于是共有 10 个孩子，可以任意把他们分成四个游戏小组，所以有 \(S(10,4)\) 种可能。

1. “合并成对”降维。每对兄弟姐妹必须同组，把一对整体当成一个不可分的单位（超级孩子），分组时它就只占“一个”位置。合并后共 10 个单位。
2. 分成四个非空、无序的小组 = \(S(10,4)\)。“分成四个游戏小组”指划分成 4 个非空块、且小组本身不编号（无序），这正是第二类 Stirling 数 \(S(10,4)\) 的定义。

第 6 题　每盒奇数个球

我们考虑等价的问题：把 50 个相同的球放入四个可区分的盒子，使每盒得到奇数个球。先在每个盒里各放 1 个球。这样还剩 46 个球，需要把它们放进四个盒子，使每盒得到偶数个球（注意不要求每盒都有球）。这等同于把 23 个相同的球放进四个可区分的盒子的方法数，所以所求的数是 \[\binom{23+4-1}{4-1}=\binom{26}{3}.\]

1. “奇数 = 1 + 偶数”。每盒至少奇数个，先垫底各放 1 个（用掉 4 个），余 \(50-4=46\)。原来每盒奇数，减去 1 后每盒变成偶数（\(\ge 0\)）。
2. 偶数 = 2 × 整数。把 46 个球按“每盒偶数”分配，等价于把成对的球分配：令每盒球数为 \(2y_i\)，则 \(y_1+y_2+y_3+y_4=23\)，\(y_i\ge0\)。这就是把 23 个相同球放进 4 个盒（可空）。
3. 隔板法。把 23 个相同球放进 4 个可区分盒（允许空），方法数为 \(\binom{23+4-1}{4-1}=\binom{26}{3}=2600\)。

第 7 题　带下界的分配化为弱合成

存在从可接受分配之集 \(S\) 到“11 拆成 6 个部分的全体弱合成”之集 \(T\) 的双射 \(f\)。事实上，若 \(a=(a_1,\dots,a_6)\) 表示一个可接受分配，即前三个 \(a_i\) 至少为 2、后三个 \(a_i\) 至少为 1，则令 \[f(a)=(a_1-2,\,a_2-2,\,a_3-2,\,a_4-1,\,a_5-1,\,a_6-1).\] 由于诸 \(a_i\) 之和为 20，\(f(a)\) 各分量之和为 11。因此所有可能数为 \[\binom{11+6-1}{6-1}=\binom{16}{5}.\]

1. “扣掉下界”是关键招式。每个变量有下界（前三个 \(\ge2\)，后三个 \(\ge1\）），就把这些下界先扣掉，化成全部 \(\ge0\) 的标准问题。
2. 新和数。扣掉的总量是 \(2\cdot3+1\cdot3=9\)，原和 \(20\) 变为 \(20-9=11\)，新变量 \(b_i=f(a)_i\ge0\) 且 \(b_1+\dots+b_6=11\)。
3. 隔板法。11 个相同球放 6 个盒（可空）：\(\binom{11+6-1}{6-1}=\binom{16}{5}=4368\)。

第 8 题　用减法原理排除“坏的”弱合成

此处用减法原理（subtraction principle）。10 拆成 4 个部分的全体弱合成共 \(\binom{13}{3}=286\) 个。我们数其中“坏的”，即含有某个 \(\ge9\) 的部分的弱合成。显然，含 10 的弱合成有 4 个。含 9 的有 12 个：9 可以处在合成的 4 个位置之一，余下的 1 可以处在剩 3 个位置之一，由乘法原理得证。于是由加法原理，10 的坏弱合成共 \(4+12=16\) 个，故好的有 \(286-16=270\) 个。

1. 总数。10 拆 4 部分弱合成 \(=\binom{10+4-1}{4-1}=\binom{13}{3}=286\)。
2. 含 10 的。某一部分等于 10，其余三部分都为 0，10 放在 4 个位置之一，共 4 个：\((10,0,0,0),(0,10,0,0),(0,0,10,0),(0,0,0,10)\)。
3. 含 9 的。某部分为 9，剩下 1 必为另一部分。9 放 4 个位置之一（4 种），1 放余下 3 个位置之一（3 种），\(4\times3=12\) 个。
4. 无重叠相加再相减。含 10 与含 9 不可能同时发生（和才 10），两类不相交，坏的共 \(16\)；好的 \(=286-16=270\)。

第 9 题　单调函数的个数

这与把 \(n\) 个相同的球（函数定义域的元素）放进 \(n\) 个可区分的盒子（函数值域的元素）相同。球分配好后，我们给它们编号 1 到 \(n\)，但由于要求函数单调，必须这样贴标签：第一个非空盒里的球得到最小的编号，第二个非空盒里的球得到次小的编号，依此类推。因此从 \([n]\) 到 \([n]\) 的单调函数个数是 \[\binom{2n-1}{n-1}.\]

1. 单调函数只由“每个值取了几次”决定。单调（不减）函数 \(f\) 一旦确定了每个值 \(j\) 被取到的次数 \(m_j\ge0\)，函数就唯一确定了（小的输入对应小的值）。所以只需数非负整数解 \(m_1+\dots+m_n=n\)。
2. 这就是球放盒。把 \(n\) 个相同球（输入）放进 \(n\) 个盒（输出值），盒里球数即该值被取的次数。
3. 隔板法。\(\binom{n+n-1}{n-1}=\binom{2n-1}{n-1}\)。

第 10 题　各部分都是 3 的倍数的合成

24 的这类合成（各部分都是 3 的倍数）之集与 8 的全体合成之集间存在双射，该双射只需把每个部分除以 3。因此所求的数就是 8 的合成个数，即 \(2^7=128\)。

1. 设 24 的合成 \((c_1,\dots,c_k)\) 各 \(c_i\) 是 3 的倍数。令 \(c_i'=c_i/3\)，则 \(c_i'\) 是正整数且 \(\sum c_i'=24/3=8\)，得到 8 的一个合成。
2. 反之，8 的合成乘以 3 即还原。双射成立，故个数 \(=\) 8 的合成数 \(=2^{8-1}=2^7=128\)（用第 3 题结论）。

第 11 题　\(x^n=\sum_k S(n,k)(x)_k\)

(a) 我们证明等式两边都在数“用 \(x\) 个字母的字母表能拼出的长度为 \(n\) 的词”。对左边，这是乘法原理（更确切地说推论 1.11）的直接结果。右边稍复杂些：我们数其中恰用 \(k\) 个不同字母的词。把词的 \(n\) 个位置分给 \(k\) 类字母有 \(S(n,k)\) 种方式；再为这些位置选定具体字母有 \((x)_k\) 种方式（注意字母的顺序有影响，所以不是 \(\binom{x}{k}\) 而是 \((x)_k\)）。由乘法原理，这样的词有 \(S(n,k)(x)_k\) 个，对所有 \(k\) 求和即得结论。

(b) (a) 的结果表明，两个 \(n\) 次多项式 \(x^n\) 与 \(\sum_{k=0}^n S(n,k)x^k\) 在无穷多个 \(x\) 值处（即所有正整数）相等。这意味着它们的差有无穷多个根。然而其差也是一个次数至多为 \(n\) 的多项式，故它要有多于 \(n\) 个根，唯一可能就是它是零多项式。

1. 左边为何是 \(x^n\)。长度 \(n\) 的词，每个位置独立从 \(x\) 个字母里选，乘法原理给 \(\underbrace{x\cdot x\cdots x}_{n}=x^n\)。
2. 右边按“用了几种字母”分类。恰用 \(k\) 种字母：先把 \(n\) 个位置划分成 \(k\) 个非空类（同类位置放同一字母）——\(S(n,k)\) 种；再给这 \(k\) 个类指派 \(k\) 个不同的具体字母，有顺序之分，故 \(x(x-1)\cdots(x-k+1)=(x)_k\) 种。
3. 求和。用了几种字母互斥，按 \(k\) 加起来：\(x^n=\sum_k S(n,k)(x)_k\)。
4. (b) 多项式恒等。两个次数 \(\le n\) 的多项式在无穷多点相等，差是次数 \(\le n\) 的多项式却有无穷多根；次数 \(\le n\) 的非零多项式至多 \(n\) 个根，矛盾，故差恒为 0，等式作为多项式对一切 \(x\) 成立。

第 12 题　Stirling 数作为基变换矩阵

全体实系数多项式构成实数域上的一个向量空间。它的一组基是 \(\{1,x,x^2,\dots\}\)，另一组基是 \(\{1,(x)_1,(x)_2,\dots\}\)。上一题的结果表明，这两组基之间的过渡矩阵就是由第二类 Stirling 数构成的无穷矩阵 \(S\)，即对一切非负整数 \(k,n\) 有 \(S_{n,k}=S(n,k)\)。\(S\) 的前几个元素如下： \[S=\begin{pmatrix}1&0&0&0&0&\cdots\\0&1&0&0&0&\cdots\\0&1&1&0&0&\cdots\\0&1&3&1&0&\cdots\\0&1&7&6&1&\cdots\\\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\end{pmatrix}.\] 换言之，若令 \(\vec{x}=(1,x,x^2,\dots)^{\mathsf T}\) 与 \(\vec{x}'=(1,(x)_1,(x)_2,\dots)^{\mathsf T}\)，则有 \(S\vec{x}'=\vec{x}\)。

1. 第 11 题已得 \(x^n=\sum_k S(n,k)(x)_k\)。这正是说：把基 \(\{(x)_k\}\) 用矩阵 \(S\) 线性组合，能得到基 \(\{x^n\}\)，故 \(S\) 是两组基之间的过渡矩阵。
2. 验证一行。第 \(n=4\) 行（从 0 计为第 5 行）系数 \(0,1,7,6,1\) 给出 \(x^4=(x)_1+7(x)_2+6(x)_3+(x)_4\)。这与 \(S(4,1)=1,S(4,2)=7,S(4,3)=6,S(4,4)=1\) 一致。

第 13 题　把 \([10]\) 分成 3,3,4 三块的划分数

把 \([10]\) 的元素排成一行，有 \(10!\) 种排法，然后在第 3 个与第 6 个元素之后各插一道竖线。这必定给出我们所需类型的一个划分。然而每个划分会被得到很多次：若把前三个元素彼此置换（\(3!\) 种）、把中间三个彼此置换（\(3!\) 种）、把最后四个彼此置换（\(4!\) 种），得到的还是同一个划分；最后，还可以把“前三元素的块”与“中间三元素的块”互换而不改变划分。因此由乘法原理，每个划分被得到 \(3!\cdot3!\cdot4!\cdot2\) 次。于是由除法原理，所需类型的 \([10]\) 划分数为 \[\frac{10!}{3!\cdot3!\cdot4!\cdot2}.\]

1. 先制造有序版本。排成一行（\(10!\)）再切成 \(3|3|4\)，得到一个“有序、块内也有序”的对象。
2. 块内顺序无关。每块内部任意重排都是同一集合，故各除以 \(3!,3!,4!\)。
3. 两个同样大小（都是 3）的块可互换。由于两块都恰好 3 个元素、且划分不区分块的先后，把这两块整体对调得到同一划分，故再除以 \(2\)。（4 元块大小独特，不参与对调。）
4. 除法原理：每个目标被重复计 \(3!\cdot3!\cdot4!\cdot2=6\cdot6\cdot24\cdot2=1728\) 次，故划分数 \(=10!/1728=3628800/1728=2100\)。

第 14 题　5 名棋手的可能名次（允许并列）

若完全没有并列，则有 \(5!=120\) 种可能结果。若恰有一组两人并列、无其他并列，则并列的两人有 \(\binom{5}{2}=10\) 种选法，之后有 \(4!\) 种可能排名，由乘法原理得 240 种可能。若有两组两人并列，则两对并列者有 \(\binom{5}{2}\binom{3}{2}/2=15\) 种选法，于是有 6 种可能排名，得 90 种不同可能。若恰有一组三人并列、无其他并列，则并列三人有 \(\binom{5}{3}=10\) 种选法，于是有 6 种可能排名，得 60 种可能。最后，若有一组三人并列加一组两人并列，则三人并列者有 \(\binom{5}{3}=10\) 种选法，于是有 2 种可能排名，得 20 种可能。因此可能结果的总数为 \[120+240+90+60+20=530.\]

1. 按“并列的形状”分类。5 人的名次结构（不并列、单个 2 并列、两个 2 并列、单个 3 并列、3+2 并列）互斥，分别数后相加。注意题目排除“超过两人的并列之外再加……”等不允许的情形，这里枚举的都是允许的形状。
2. 一组两人并列。选并列对 \(\binom{5}{2}=10\)；把这对当一个单位，连同其余 3 人共 4 个单位排名次 \(4!=24\)：\(10\times24=240\)。
3. 两组两人并列。选第一对 \(\binom{5}{2}\)、第二对 \(\binom{3}{2}\)，但两对地位对称要除以 \(2!\)：\(\binom{5}{2}\binom{3}{2}/2=10\cdot3/2=15\)；现有 3 个单位（两个对 + 一个单人）排名次 \(3!=6\)：\(15\times6=90\)。
4. 一组三人并列。选三人 \(\binom{5}{3}=10\)；三人当一单位连同其余 2 人共 3 单位 \(3!=6\)：\(10\times6=60\)。
5. 三人并列 + 两人并列。选三人 \(\binom{5}{3}=10\)（余下两人自动成对）；两个单位（三人组、两人组）排名次 \(2!=2\)：\(10\times2=20\)。
6. 合计 \(120+240+90+60+20=530\)。

第 15 题　Bell 数递推 \(B(n+1)=\sum_k \binom{n}{k}B(k)\)

设含元素 \(n+1\) 的那个块还另含 \(n-k\) 个元素。则有 \(\binom{n}{n-k}=\binom{n}{k}\) 种方法选这些元素，之后有 \(B(k)\) 种方法划分 \([n+1]\) 的其余部分。结论由加法原理与对所有 \(k\) 求和得到。

1. 盯住元素 \(n+1\)。任何 \([n+1]\) 的划分里，\(n+1\) 必在某个块内。设该块除 \(n+1\) 外还有 \(n-k\) 个元素，则块外还剩 \(k\) 个元素。
2. 两步计数。从 \([n]\) 中选出与 \(n+1\) 同块的 \(n-k\) 个元素：\(\binom{n}{n-k}=\binom{n}{k}\) 种；剩下的 \(k\) 个元素任意划分：\(B(k)\) 种。
3. 对 \(k\) 求和。\(k\) 从 0 到 \(n\) 互斥穷尽，得 \[B(n+1)=\sum_{k=0}^{n}\binom{n}{k}B(k).\]

第 16 题　“至多 \(k\) 个部分”与“部分不超过 \(k\)”的分拆数相等

断言这两类分拆之间存在一个简单的双射，更确切地说，是它们的 Ferrers 图之间的双射。事实上，\(n\) 分成至多 \(k\) 个部分的分拆，对应于 \(n\) 个方格、至多 \(k\) 行的 Ferrers 图；\(n\) 分成每部分不超过 \(k\) 的分拆，对应于 \(n\) 个方格、至多 \(k\) 列的 Ferrers 图。所以取共轭（转置）就是这两个集合之间的双射。

1. Ferrers 图。分拆 \((a_1\ge a_2\ge\dots)\) 画成左对齐的方格，第 \(i\) 行 \(a_i\) 个格。行数 = 部分个数；最长行的长度 = 最大部分。
2. 共轭 = 转置。把图沿主对角线翻转，行变列。原图“至多 \(k\) 行”\(\Leftrightarrow\) 共轭图“至多 \(k\) 列”\(\Leftrightarrow\) 共轭分拆“每部分 \(\le k\)”。这是一一对应，故两类分拆个数相等。

第 17 题　14 分成 4 个相异部分

设 \((a_1,a_2,a_3,a_4)\) 是 14 的一个这样的分拆（4 个相异部分，\(a_1>a_2>a_3>a_4\ge1\)）。则 \((a_1-3,a_2-2,a_3-1,a_4)\) 是 8 的一个分拆。反之，若 \((b_1,b_2,b_3,b_4)\) 是 8 的分拆，则 \((b_1+3,b_2+2,b_3+1,b_4)\) 是 14 分成 4 个相异部分的分拆。因此所求的数就是 8 分成 4 个部分的分拆数。这样的分拆有 5 个，即 \((5,1,1,1),(4,2,1,1),(3,3,1,1),(3,2,2,1),(2,2,2,2)\)。

1. 减阶梯把“相异”变“可等”。相异且递减意味着相邻差 \(\ge1\)。减去阶梯 \((3,2,1,0)\) 后，严格递减放松为不增，且各项 \(\ge1\)，得到 8 的普通 4 部分分拆。和数从 14 减少 \(3+2+1+0=6\)，变 8。
2. 逐一列举 8 的 4 部分分拆。要求 \(b_1\ge b_2\ge b_3\ge b_4\ge1\)，\(\sum=8\)：\((5,1,1,1),(4,2,1,1),(3,3,1,1),(3,2,2,1),(2,2,2,2)\)，恰 5 个。
3. 验证一例。\((2,2,2,2)\to(2{+}3,2{+}2,2{+}1,2)=(5,4,3,2)\)，确为 14 的 4 个相异部分分拆。

第 18 题　唯一没有自共轭分拆的 \(n\)

唯一这样的整数是 \(2\)。事实上，若 \(n=2k+1\)，则由一行与一列、长度都为 \(k+1\) 的分拆是自共轭的；若 \(n=2k+4\)，则由长 \(k+2\) 的一行、长 \(k+2\) 的一列、再加一条长 2 的第二行所构成的分拆是自共轭的。两种构造对 \(k\ge0\) 都成立，于是只剩 \(n=2\) 这个例外。建议读者基于补充习题 19 的结果，寻找另一种证明。

1. 自共轭 = 转置后不变。需要 Ferrers 图关于主对角线对称。
2. 奇数 \(n=2k+1\)：直角钩。取一行 \(k+1\) 格、一列 \(k+1\) 格，共用角上 1 格，总格数 \((k+1)+(k+1)-1=2k+1=n\)。这个“L 形钩”关于对角线对称，自共轭。
3. \(n=2k+4\)：钩 + 一条长 2 的第二行。第一行长 \(k+2\)、第一列长 \(k+2\)（共角，\(2k+3\) 格），再添第二行 2 格（与第二列对称），共 \(2k+3+1=2k+4=n\)，仍对称。
4. 覆盖范围。奇数全覆盖；\(2k+4\)（\(k\ge0\)）覆盖 \(4,6,8,\dots\) 所有 \(\ge4\) 的偶数。剩下偶数只有 \(n=2\) 没被构造覆盖——而 2 确实无自共轭分拆（其分拆只有 \((2)\) 与 \((1,1)\)，互为共轭但都不自共轭）。

第 19 题　\(p_k(kn)\) 是 \(n\) 的 \(k-1\) 次多项式

(a) 断言此多项式的次数为 \(k-1\)。我们将对 \(k\) 用归纳法证明这一点以及 \(p_k(kn)\) 是多项式这一事实。当 \(k=1\) 时，等式 \(p_k(kn)=1\) 成立，命题为真。否则，断言 \[p_k(kn)=p_{k-1}(kn)+p_k\big((n-1)k\big).\tag{2.12}\] 事实上，被左边计数的一个分拆，要么少于 \(k\) 个部分——此时它被右边第一项计数，要么恰有 \(k\) 个部分——此时把它每个部分减 1，得到一个被右边第二项计数的分拆。整理后得 \[p_k(kn)-p_k\big((n-1)k\big)=p_{k-1}(kn).\tag{2.13}\] 换言之，由归纳假设，\(p_k(kn)\) 相邻两个值之差是次数为 \(k-2\) 的多项式。这就推出 \(p_k(kn)\) 是 \(k-1\) 次多项式。建议读者对 \(k\) 用归纳法证明本命题。

(b) 与 (a) 类似，只需把 (2.12) 换成 \[p_k(kn+r)=p_{k-1}(kn+r)+p_k\big((n-1)k+r\big).\tag{2.14}\]

1. 记号。\(p_k(m)\) 是 \(m\) 分成至多 \(k\) 个部分的分拆数。
2. (2.12) 的分类。计数 \(m=kn\) 的至多 \(k\) 部分分拆：(i) 部分数 \(
3. 差分降次。(2.13) 说 \(p_k(kn)\) 的“相邻差”\(=p_{k-1}(kn)\)。归纳假设 \(p_{k-1}\) 是 \(k-2\) 次多项式；一个序列若其一阶差分是 \(k-2\) 次多项式，则该序列本身是 \(k-1\) 次多项式（积分/求和把次数升 1）。
4. (b) 带余数 \(r\)。对一般 \(m=kn+r\)（\(0\le r

第 20 题　分拆数 \(p(n)\) 增长快于任何多项式

反设结论不真，即设存在多项式 \(q(n)\) 使 (2.11) 不成立。设 \(q\) 的次数为 \(k-2\)。注意对任何 \(n>k\) 有 \(p(n)>p_k(n)\)。另一方面，上一题表明 \(p_k(n)\) 可由 \(k\) 个多项式描述，每个次数为 \(k-1\)，对应模 \(k\) 的每个剩余类。因此连 \(p_k(n)\) 都比 \(q(n)\) 增长更快，从而 \(p(n)\) 也是如此。

注意，像 \(p_k(n)\) 这样的函数，即由 \[f(n)=\begin{cases}f_0(n)&\text{若 }n=kr,\\f_1(n)&\text{若 }n=kr+1,\\\ \cdots\\f_{k-1}(n)&\text{若 }n=kr+(k-1)\end{cases}\] 定义、其中诸 \(f_i\) 为多项式的函数，称为拟多项式（quasi-polynomial）。群论中有人把它们称为“剩余类上的多项式”或 porc。

1. 下界 \(p(n)>p_k(n)\)。\(p(n)\) 数全部分拆，\(p_k(n)\) 只数至多 \(k\) 部分的分拆；当 \(n>k\) 时还有部分数超过 \(k\) 的分拆，故严格更多。
2. \(p_k(n)\) 已超越 \(q\)。由第 19 题，\(p_k(n)\) 在每个剩余类上是 \(k-1\) 次多项式；而 \(q\) 只有 \(k-2\) 次。高一次的多项式终将超过低次的，故 \(p_k(n)\) 增长快于 \(q(n)\)，\(p(n)\) 更甚——与假设矛盾。
3. 拟多项式就是“按 \(n\) 除以 \(k\) 的余数分段、每段是普通多项式”的函数。

第 21 题　映射 \(g\) 与 \(k(g(s))=\mathrm{least}(s)\)

设 \(s=(s_1,s_2,\dots,s_u)\)。我们给 \(a\) 的前 \(\mathrm{least}(s)\) 个部分各加了 1。在此之前，这些部分是连续整数，因此相加后它们仍连续。另一方面，由于 \(\mathrm{least}(s)<\mathrm{stair}(s)\)，原本有 \(\mathrm{stair}(s)=\mathrm{least}(s)+1\)，故有 \(s_{\mathrm{least}(s)+1}=s_{\mathrm{least}(s)}-1\)。我们没有增加 \(s_{\mathrm{least}(s)+1}\)，却增加了 \(s_{\mathrm{least}(s)}\)，于是在第 \(\mathrm{least}(s)\) 个部分处打断了“连续整数”这一串。这表明 \(k(g(s))=\mathrm{least}(s)\)。

为证第二个论断，注意 \(s\) 的各部分两两相异。特别地，\(s\) 的倒数第二个部分 \(s_{u-1}\) 大于 \(\mathrm{least}(s)=k(g(s))\)。结论随之得到，因为或者 \(l(g(s))=s_{u-1}\)，或者 \(l(g(s))=s_{u-1}+1\)。

1. 背景。本题属于一个分拆双射的技术性引理：\(\mathrm{least}(s)\) 是“从开头起、连续整数那一串的长度”，\(\mathrm{stair}(s)\) 是相关阶梯量；\(g\) 是构造中的一步操作，\(k(\cdot),l(\cdot)\) 读取某些参数。
2. 核心逻辑：在何处“断开连续串”。给前 \(\mathrm{least}(s)\) 项各 \(+1\)，它们内部仍连续；但第 \(\mathrm{least}(s)\) 项被抬高、第 \(\mathrm{least}(s)+1\) 项没动，二者之间原本相差 1 的连续关系被破坏。所以“连续串”恰在第 \(\mathrm{least}(s)\) 项处断开，即 \(k(g(s))=\mathrm{least}(s)\)。
3. 第二论断。由各部分相异，\(s_{u-1}>\mathrm{least}(s)\)；\(l(g(s))\) 只可能取 \(s_{u-1}\) 或 \(s_{u-1}+1\)，两种情况都成立。

第 22 题　\(g(s)\) 的最后一行与递减连续序列

第一个论断是平凡的，因为我们定义 \(g(s)\) 的最后一行时，是从前 \(\mathrm{stair}(s)\) 行各取一个方格而来。要看出第二个论断，注意把一个递减连续整数序列的每个元素减 1，结果仍是一个递减连续整数序列。

1. 第一论断。“最后一行”由前 \(\mathrm{stair}(s)\) 行各贡献一格拼成，其长度自然等于 \(\mathrm{stair}(s)\)，由构造直接得到，无需额外论证。
2. 第二论断（平移不变）。若 \(c,c-1,c-2,\dots\) 是递减且相邻差 1 的连续序列，整体减 1 得 \(c-1,c-2,\dots\)，仍是递减连续序列。差分（相邻差）不因整体平移而改变，所以“连续”性质保持。

第 23 题　五边形数的两两不等

首先，不可能有 \(a(3a+1)=b(3b+1)\) 或 \(a(3a-1)=b(3b-1)\)，因为函数 \(f(m)=m(3m+1)\) 与 \(g(m)=m(3m-1)\) 在正整数上都严格单调。其次，也不可能有 \(a(3a+1)=b(3b-1)\)，因为该方程等价于 \(b-a=\tfrac13\)。

1. 同型不相等。\(f(m)=m(3m+1)=3m^2+m\) 关于 \(m\ge1\) 严格递增，故 \(a\ne b\Rightarrow f(a)\ne f(b)\)；\(g\) 同理。
2. 异型不相等。设 \(a(3a+1)=b(3b-1)\)，即 \(3a^2+a=3b^2-b\)。移项 \(3(a^2-b^2)+(a+b)=0\)，即 \((a+b)(3(a-b)+1)=0\)。因 \(a+b>0\)，必有 \(3(a-b)+1=0\)，即 \(a-b=-\tfrac13\)（等价 \(b-a=\tfrac13\)），不是整数，矛盾。
3. 意义。这保证广义五边形数 \(\tfrac{m(3m\pm1)}{2}\) 两两不同，是 Euler 五边形数定理中“无重叠”的关键。

第 24 题　相异部分分拆 ↔ 逐次秩为 1 的分拆

\(n\) 分成相异部分的分拆数，等于 \(2n\) 分成相异偶数部分的分拆数（只需把每个部分乘 2）。设 \(S\) 为后者之集，\(T\) 为“\(2n\) 的、每个逐次秩（successive rank）都为 1 的分拆”之集。我们定义双射 \(f:S\to T\) 如下：设 \(s\in S\)，其首部分 \(s_1\) 为偶数，记 \(s_1=2h\)。开始构造一个 Ferrers 图：取长 \(h+1\) 的第一行与长 \(h\) 的第一列。由于角上重叠，这恰用去 \(2h=s_1\) 个方格。然后继续：若 \(s\) 的第二部分 \(s_2=2i\)，则在已建图形上加一条长 \(i+1\) 的第二行与一条长 \(i\) 的第二列（不计已有的方格），依此类推。当用完 \(s\) 的所有部分时，便得到 \(2n\) 个方格、每个逐次秩都为 1 的 Ferrers 图。令 \(f(s)\) 为该图对应的分拆（见图 2.16，把各部分变成 L 形“条纹”）。证明 \(f\) 是双射这一容易的任务留给读者。

1. 第一步双射：相异部分 ↔ 相异偶部分。把 \(n\) 的相异部分分拆每项乘 2，得到 \(2n\) 的相异偶部分分拆；除以 2 即还原。一一对应。
2. 逐次秩。分拆的第 \(j\) 个逐次秩 = 第 \(j\) 行长 − 第 \(j\) 列长（在 Ferrers 图中）。“逐次秩处处为 1”即每个 L 形钩的“行比列多 1 格”。
3. L 形拼装。偶数 \(2h\) 拆成“行 \(h+1\) + 列 \(h\) − 角 1”\(=2h\)，这条 L 钩的行长比列长正好多 1，逐次秩为 1。逐条嵌套即得 \(T\) 中的图。每个偶部分对应一条钩，钩与部分一一对应，故 \(f\) 是双射。

第 25 题　握手数与度序列分拆

(a) 设聚会上每对互相认识的人握手一次。若握手总次数为 \(m\)，则我们关心的和为 \(2m\)，因为每次握手涉及两个人。换言之，把记下的数字加起来时，每次握手被计两次，每个参与者各计一次。

(b) 不。设 \(A\) 是公司里认识人最多的人，公司有 \(n\) 人。则分拆 \(p\) 第一行的长度就是 \(A\) 认识的其他人数（故 \(

(c) 不。设 \(B\) 是除 \(A\) 外认识人最多的人。则第二行长度是 \(B\) 认识的人数 \(|B|\)。设 \(|A|+|B|=n+t\)，这表示至少有 \(t\) 人同时认识 \(A\) 与 \(B\)，因此第二列长度至少为 \(t+2\)（因 \(A,B\) 也各认识至少两人）。于是前两行之和为 \(n+t\)，前两列之和至少为 \(n+t+2\)，所以 \(r_1+r_2\le -2\)。

注意，结论甚至更强。著名的 Erdős–Gallai 判据说，能充当 \(p\) 的分拆恰好是那些满足 \[r_1+r_2+\dots+r_i\le -i,\qquad \forall\,i\in[k]\] 的分拆，其中 \(k\) 是 \(p\) 的 Durfee 方块的边长。

1. (a) 双重计数。把每个人“认识的人数”加起来，相当于数有序对（人, 他认识的人）。每条认识关系（=每次握手）涉及两个人，被两端各数一次，故总和 \(=2m\)，必为偶数。
2. (b) 逐次秩 \(r_i\)=第 \(i\) 行−第 \(i\) 列。取度最大者 \(A\)：他认识 \(
3. (c) 前两秩之和 \(\le-2\)。第二大度者 \(B\) 贡献第二行 \(|B|\)；同时认识 \(A,B\) 的人数 \(\ge t=|A|+|B|-n\)，使第二列 \(\ge t+2\)。把前两行和（\(n+t\)）与前两列和（\(\ge n+t+2\)）相减得 \(r_1+r_2\le-2\)。
4. 一般地，Erdős–Gallai 给出度序列“可实现”的充要条件 \(\sum_{i\le j}r_i\le-j\)。

第 26 题　Durfee 方块为 2 时自共轭图格数为偶

由于 \(p\) 的第三个部分是 2，\(p\) 的 Durfee 方块大小为 2。因为取共轭保持 \(2\times2\) 的 Durfee 方块不变，所以具有此 Durfee 方块的自共轭 Ferrers 图中的方格数是偶数。

1. Durfee 方块是 Ferrers 图左上角能放下的最大正方形。第三部分 \(=2\) 意味着至少 3 行、每行至少 2 格，但第 3 行只有 2 格无法支撑 \(3\times3\)，故 Durfee 方块边长恰为 2。
2. 对称性给出偶数。自共轭图关于对角线对称。\(2\times2\) 的 Durfee 方块自身对称（4 格）；方块之外的部分被对角线成对地分为“右侧”与“下侧”两块互为镜像，格数相等，合起来为偶数。偶数（方块 4 格）+ 偶数（镜像两块）= 偶数。

第 27 题　相同数字不相邻的排列数

我们改为数“有两个相同数字落在相邻位置”的排列。先数其中两个 1 相邻的，记为集合 \(A\)。把两个 1 替换成一个符号 S，可见 \(|A|=6!/2\)。同理，若 \(B\) 是两个 2 相邻的排列之集，则同样 \(|B|=6!/2\)。最后 \(|A\cap B|=5!\)，因为可把两个 1 替换成 S、两个 2 替换成 T。于是引理 2.32 给出 \(|A\cup B|=6!-5!\)（即 \(6!/2+6!/2-5!\)）。因此由减法原理，该多重集中相同数字不相邻的排列数为 \[\frac{7!}{2\cdot2}-(6!-5!).\]

1. 总数。多重集含两个 1、两个 2，及另外三个互不相同的数字，共 7 个、两组各重复 2 次，可区分排列数 \(=\dfrac{7!}{2!\,2!}=\dfrac{7!}{4}\)。
2. \(|A|\)：两个 1 相邻。把“11”捆成单一符号 S，连同其余 5 个（含两个 2）共 6 个对象排列，但两个 2 仍重复，\(|A|=\dfrac{6!}{2!}=6!/2\)。\(|B|\) 同理。
3. \(|A\cap B|\)：两个 1 且两个 2 都相邻。“11”→S、“22”→T，连同其余 3 个共 5 个全不同对象，\(5!\)。
4. 容斥（引理 2.32）。坏排列 \(=|A\cup B|=|A|+|B|-|A\cap B|=6!/2+6!/2-5!=6!-5!\)。
5. 减法原理。好排列 \(=\dfrac{7!}{4}-(6!-5!)=1260-(720-120)=1260-600=660\)。

第 28 题　带额外限制的 \([10]\) 划分计数

显然，对例 2.36 而言坏的所有 \([10]\) 划分，在此也是坏的。然而还有额外的坏划分，即那些以 \(\{1,2\}\) 为一个块、或以 \(\{1,3\}\) 为块、或以 \(\{2,3\}\) 为块、或以 \(\{1,2,3\}\) 为块的划分。幸运的是，这些划分集合两两不相交，故由加法原理，它们的总数为 \(3B(8)+B(7)\)。因此坏划分的总数等于这个数加上例 2.36 中的坏划分数，即 \(3B(9)+2B(7)\)。于是好划分数为 \[B(10)-3B(9)-2B(7).\]

1. 计数“某指定块固定”的划分。若强行规定 \(\{1,2\}\) 必须自成一块，则把它当一个单位，余下 8 个元素（\(3,\dots,10\)）任意划分，共 \(B(8)\) 个。三种两元块 \(\{1,2\},\{1,3\},\{2,3\}\) 各贡献 \(B(8)\)，共 \(3B(8)\)；\(\{1,2,3\}\) 自成一块则余 7 元任意划分 \(B(7)\)。
2. 互斥。这四类条件不能同时成立（如 \(\{1,2\}\) 与 \(\{1,3\}\) 同为块会冲突），故直接相加 \(3B(8)+B(7)\)。
3. 合并例 2.36 的坏划分得总坏数（书中记为 \(3B(9)+2B(7)\)），从全体 \(B(10)\) 中减去，得好划分数 \(B(10)-3B(9)-2B(7)\)。

第 29 题　与 56 不互素的整数（容斥）

设 \(A_1\) 为 \([1000]\) 中与 7 不互素的整数之集；设 \(A_2\) 为与 8 不互素（等价地，为偶数）的整数之集。则 \(|A_2|=500\)。由于 \(A_1\) 由可被 7 整除的正整数组成，\(|A_1|=\lfloor1000/7\rfloor=142\)。最后，\(A_1\cap A_2\) 是 \([1000]\) 中可被 14 整除的正整数之集，故 \(|A_1\cap A_2|=\lfloor1000/14\rfloor=71\)。因此由引理 2.32， \[|A_1\cup A_2|=142+500-71=571.\]

1. 与 8 不互素 = 偶数。\(8=2^3\)，与 8 有公因子等价于含因子 2，即为偶数。\([1000]\) 中偶数有 \(1000/2=500\) 个。
2. 与 7 不互素 = 7 的倍数。7 是素数，与 7 有公因子等价于是 7 的倍数。个数 \(\lfloor1000/7\rfloor=142\)。
3. 交集 = 14 的倍数。同时是 2 与 7 的倍数 = 14 的倍数，\(\lfloor1000/14\rfloor=71\)。
4. 容斥。\(|A_1\cup A_2|=142+500-71=571\)。（若题目要的是“与 56 互素”的个数，则为 \(1000-571=429\)。）

第 30 题　四种语言、任意三人有共同语言

断言每名员工至少会说三种语言。反设其反，即 Albert 只会英语和西班牙语。公司里有人不会英语，记为 Bella。则 Bella 必会西班牙语，否则 Albert、Bella 与任何第三人都会违反条件。然而公司里有人不会西班牙语，记为 Christine，于是 Albert、Bella、Christine 没有共同语言。

给出这样一个公司的例子：设公司有任意多名员工，分成五个非空组 \(A,B,C,D,E\)。设 \(A\) 是不会英语的组，\(B\) 是不会西班牙语的组，\(C\) 是不会德语的组，\(D\) 是不会法语的组，\(E\) 是会全部四种语言的组。因为人人至少会三种语言，没人属于两个组。于是无论怎样选三人，前四组中总有至少一组没被选到，所选的三人都会说该组不会说的那种语言。

1. 必要性（反证）。若某人只会两种语言（如英、西），则存在不会英语者 Bella；若 Bella 又不会西语，则 {Albert, Bella, 任意人} 无共同语言，违例，故 Bella 会西语；但又存在不会西语者 Christine，于是 {Albert, Bella, Christine} 无共同语言。矛盾。故人人至少会 3 种（即每人恰缺至多 1 种）。
2. 充分性（构造）。按“恰缺哪一种语言”把人分到 \(A,B,C,D\)（缺英/西/德/法），\(E\) 为全会者。任取三人，他们至多覆盖三种“缺失”，必有某种语言四个组里没人缺——这三人都会，故有共同语言。

第 31 题　容斥右端不计入不属于任何 \(A_i\) 的元素

若 \(x\) 不属于任何 \(A_i\)，则右端的每一项都不计数它，因此它们的和也不计数它。

1. 容斥公式右端的每一项都是若干个 \(A_i\) 的交集的大小（带正负号）。若 \(x\) 不在任何 \(A_i\) 里，它就不在任何交集里，每项都把它计 0 次。
2. 0 的带符号求和仍是 0，故 \(x\) 在右端被计 0 次——与左端（只数“属于某些 \(A_i\)”的元素）一致。

第 32 题　\(\sum_i \binom{n}{i}D(i)=n!\)

我们有 \[\sum_{i=0}^{n}\binom{n}{i}D(i)=\sum_{i=0}^{n}\binom{n}{n-i}D(i)=n!.\] 事实上，长度为 \(n\) 的排列有 \(n!\) 个；其中恰有 \(n-i\) 个不动点、其余 \(i\) 个位置构成错位排列的排列有 \(\binom{n}{n-i}D(i)\) 个。

1. 按不动点个数分类。任一 \([n]\) 排列，设它有恰好 \(j=n-i\) 个不动点。选这 \(j\) 个不动点：\(\binom{n}{j}=\binom{n}{n-i}=\binom{n}{i}\) 种。
2. 其余 \(i\) 个无不动点。剩下 \(i\) 个元素必须各自不在原位，即构成一个错位排列，有 \(D(i)\) 种。
3. 求和穷尽。\(i\) 从 0 到 \(n\) 把全体排列不重不漏地分类，故 \(\sum_i\binom{n}{i}D(i)=n!\)。

第 33 题　“恰属于 \(n-2\) 个 \(A_i\)”的容斥公式

我们证明右端也在数恰属于 \(n-2\) 个 \(A_i\) 的元素。若 \(x\) 恰含于 \(n-2\) 个 \(A_i\)，则它被右端第一项计 1 次、被另两项各计 0 次。若 \(x\) 恰含于 \(n-1\) 个 \(A_i\)，则它被第一项计 \(\binom{n-1}{n-2}=n-1\) 次，又被第二项减去 \(n-1\) 次；第三项计 0 次，故合计被计 1 次。最后，若 \(x\) 属于全部 \(A_i\)，则第一项计 \(\binom{n}{n-2}=\binom{n}{2}\) 次，第二项减去 \((n-1)\binom{n}{n-1}=(n-1)n\) 次，第三项计 \(\binom{n}{2}\) 次。然而 \[\binom{n}{2}-(n-1)n+\binom{n}{2}=0,\] 这就完成了“右端恰好把每个具所需性质的元素计 1 次”的证明。

1. 目标。验证某个交替和恰好计数“恰属于 \(n-2\) 个集合”的元素——对这种元素计 1，其余计 0。
2. 逐档检验。设 \(x\) 恰属于 \(t\) 个 \(A_i\)。\(t=n-2\)：第一项 \(\binom{t}{n-2}=1\)，余 0，合计 1。\(t=n-1\)：第一项 \(\binom{n-1}{n-2}=n-1\)，第二项减 \(n-1\)，合计 0。\(t=n\)：见下式。
3. \(t=n\) 用恒等式归零。\(\binom{n}{2}+\binom{n}{2}=n(n-1)=(n-1)n\)，故 \(\binom{n}{2}-(n-1)n+\binom{n}{2}=0\)，合计 0。所有非目标档都计 0，目标档计 1，公式正确。

第 34 题　“恰属于 \(n-3\) 个 \(A_i\)”的容斥公式

证明与上一题非常相似。可同样验证：恰属于 \(n-3\)、\(n-2\) 或 \(n-1\) 个 \(A_i\) 的每个元素在右端都被计恰 0 次。对属于全部 \(A_i\) 的元素，这由恒等式 \[\binom{n}{3}-(n-2)\binom{n}{2}+n\binom{n-1}{2}-\binom{n}{3}=0\] 推出。

1. 同法分档。设 \(x\) 恰属于 \(t\) 个集合，对 \(t=n-3\)（计 1）、\(t=n-2,n-1\)（计 0），逐项核对，与第 33 题完全平行。
2. \(t=n\) 的四项相消。把 \(\binom{n}{3},-(n-2)\binom{n}{2},+n\binom{n-1}{2},-\binom{n}{3}\) 相加。两个 \(\binom{n}{3}\) 抵消，余 \(-(n-2)\binom{n}{2}+n\binom{n-1}{2}\)。因为 \((n-2)\binom{n}{2}=\dfrac{(n-2)n(n-1)}{2}=n\binom{n-1}{2}\)，故和为 0。

第 35 题　恰属于 \(k\) 个集合的元素数 \(B_k\)

我们断言 \[B_k=\sum_{i=k}^{n}(-1)^{i-k}\binom{i}{k}D_i.\] 设 \(x\) 是恰含于 \(t\) 个集合 \(A_i\) 的元素。则有三种可能。

(a) 若 \(t

(b) 若 \(t=k\)，则右端唯一计 \(x\) 的项是 \(i=k\) 那一项，其值为 \(\binom{k}{k}D_k=D_k\)，故 \(x\) 被右端恰计 1 次。

(c) 若 \(t>k\)，则对满足 \(k\le i\le t\) 的任何 \(i\)，被 \(D_i\) 计数的 \(A_i\) 的 \(i\) 重交集中有 \(\binom{t}{i}\) 个含 \(x\)。因此 \(x\) 被右端计 \[\sum_{i=k}^{t}(-1)^{i-k}\binom{t}{i}\binom{i}{k}\] 次。利用第 1 章补充习题 16(b)，上式等于 \[\sum_{i=k}^{t}(-1)^{i-k}\binom{t}{k}\binom{t-k}{i-k}=\binom{t}{k}\sum_{i=k}^{t}(-1)^{i-k}\binom{t-k}{i-k}=\binom{t}{k}(1-1)^{t-k}=0,\] 其中最后一步用了二项式定理以及 \(t-k>0\) 这一事实。

1. 记号。\(D_i\) = 所有 \(i\) 重交集 \(|A_{j_1}\cap\dots\cap A_{j_i}|\) 之和；\(B_k\) = 恰属于 \(k\) 个集合的元素个数。
2. 关键吸收恒等式。\(\binom{t}{i}\binom{i}{k}=\binom{t}{k}\binom{t-k}{i-k}\)（先从 \(t\) 个里选 \(i\) 个再选 \(k\) 个 = 先选最终的 \(k\) 个、再从剩 \(t-k\) 个里补 \(i-k\) 个）。
3. (c) 求和归零。提出 \(\binom{t}{k}\)，令 \(j=i-k\)，得 \(\binom{t}{k}\sum_{j=0}^{t-k}(-1)^j\binom{t-k}{j}=\binom{t}{k}(1-1)^{t-k}=0\)（因 \(t-k\ge1\)）。所以 \(t>k\) 的元素净计 0。
4. 综合：只有 \(t=k\) 的元素被计 1 次，其余计 0，故右端恰为 \(B_k\)。

第 36 题　无限交为空、有限交无穷的集合族

设 \(F_i\) 为可被 \(i\) 整除的全体正整数之集。则无论怎样选取无穷多个 \(F_i\)，它们的交总是空集，因为没有正整数有无穷多个因子。另一方面，若只选有限个 \(F_i\)，比如 \(i_1,i_2,\dots,i_n\)，则它们的交是无穷的，因为它包含所有可被 \(i_1 i_2\cdots i_n\) 整除的正整数。

另解：取 \(F_i=[i,\infty)\)。容易验证两个要求都满足。

1. 无穷交为空。设取了无穷多个不同的 \(F_{i}\)。若有正整数 \(x\) 落在全部之中，则 \(x\) 要被无穷多个不同的 \(i\) 整除——但 \(x\) 的正因子只有有限个，矛盾。故无穷交 \(=\varnothing\)。
2. 有限交无穷。选有限个 \(F_{i_1},\dots,F_{i_n}\)，它们的交含所有 \(i_1\cdots i_n\) 的倍数，这样的倍数有无穷多个。
3. 另解 \([i,\infty)\)。无穷多个 \([i,\infty)\)（\(i\) 取遍正整数）的交为空（任何固定数 \(x\) 都小于某个 \(i\)）；有限个的交是 \([\max i_j,\infty)\)，无穷大。

第 37 题　用容斥证明命题 2.44（Euler 函数）

设 \(A_i\) 为 \([n]\) 中可被 \(p_i\) 整除的元素之集。则 \(|A_i|=n/p_i\)，更一般地， \[|A_{i_1}\cap A_{i_2}\cap\dots\cap A_{i_r}|=\frac{n}{p_{i_1}p_{i_2}\cdots p_{i_r}}.\] 应用容斥原理，结论随之而来，因为由标准的代数运算， \[\prod_{i=1}^{t}(p_i-1)=\sum_{j=0}^{t}(-1)^{j}\sum_{\substack{K\subseteq\{1,\dots,t\}\\ |K|=t-j}}\;\prod_{k\in K}p_k.\]

1. 设定。设 \(n=p_1^{a_1}\cdots p_t^{a_t}\)，\(A_i\) 为 \([n]\) 中 \(p_i\) 的倍数。\(p_i\) 的倍数在 \([n]\) 中有 \(n/p_i\) 个；\(p_{i_1},\dots,p_{i_r}\) 的公倍数即 \(p_{i_1}\cdots p_{i_r}\) 的倍数，有 \(\dfrac{n}{p_{i_1}\cdots p_{i_r}}\) 个。
2. 容斥求“与 \(n\) 互素”的个数。与 \(n\) 互素 = 不被任何 \(p_i\) 整除 = 不属于任何 \(A_i\)。由容斥 \[\varphi(n)=n-\sum_i\frac{n}{p_i}+\sum_{i
3. 代数恒等式的来历。把 \(\prod_i(p_i-1)\) 展开，每个因子选 \(p_i\) 或选 \(-1\)；选出的 \(p_i\) 下标集为 \(K\)，对应项 \(\prod_{k\in K}p_k\cdot(-1)^{t-|K|}\)。按 \(|K|\) 归并即得上式，它正是 \(n\prod(1-1/p_i)\) 通分后的分子结构，从而得到 \(\varphi(n)=n\prod_i(1-1/p_i)\)。

---

返回 全书目录