2.8　习题Exercises

本页为译文 + 高中讲解合一：黑色正文为习题的忠实翻译；彩色框（解题思路 / 分步推演 / 例）与配图为面向高中生的方法提示，只给出从哪入手、用哪条原理，不必给出完整最终答案（完整解答见对应的“习题解答”一节）。

1. 称函数 \(f:S\to T\) 为单射（injection），如果它把不同的元素映到不同的元素，即 \(x\neq y\) 蕴含 \(f(x)\neq f(y)\)；称 \(f:S\to T\) 为满射（surjection），如果对每个 \(t\in T\) 都存在 \(s\in S\) 使 \(f(s)=t\)。

   1. 若一个函数既是单射又是满射，那么我们已经给它定义过一个名字。这个名字是什么？
   2. 从 \([n]\) 到 \([k]\) 的单射有多少个？
   3. 从 \([n]\) 到 \([k]\) 的满射有多少个？
   解题思路(a) 既单又满即双射（bijection）。(b) 单射要求像两两不同，按定义域逐个赋值并用乘法原理。(c) 满射不能直接乘，需借助第二类斯特林数。
   1. (b) 给 \(1\) 选像有 \(k\) 种；给 \(2\) 选像必须避开已用的 \(1\) 个，有 \(k-1\) 种；……给 \(n\) 选像有 \(k-n+1\) 种。相乘得下降阶乘 \(k(k-1)\cdots(k-n+1)=\dfrac{k!}{(k-n)!}\)（当 \(n>k\) 时为 \(0\)）。
   2. (c) 满射等价于把 \([n]\) 划分成 \(k\) 个非空块再贴上 \(k\) 个标签：先分块得 \(S(n,k)\) 种，再给 \(k\) 个块排标签得 \(k!\) 种，故满射数为 \(k!\,S(n,k)\)。

2. 用如下方法证明：\([k]\) 上的 \(n\) 元多重集（multiset）的个数为 \(\dbinom{n+k-1}{n}\)。对每个 \([k]\) 上的 \(n\) 元多重集 \(A\)，把它的元素 \(a_i\) 按非降顺序排列，使其满足不等式链

   \[1\le a_1\le a_2\le\cdots\le a_n\le k.\]

   再观察到 \([n+k-1]\) 的 \(n\) 元子集 \(B=\{b_1,b_2,\dots,b_n\}\) 满足不等式链

   \[1\le b_1通过在满足上述两条不等式链的 \(n\) 元组之间找出一个双射来完成证明。
   解题思路关键是把“可以相等的 \(\le\)”改造成“严格递增的 \(<\)”，办法是给后面的项依次加上一个递增的偏移量，从而把重复挤开。
   1. 令 \(b_i=a_i+(i-1)\)。则 \(b_1=a_1\ge1\)，\(b_n=a_n+(n-1)\le k+n-1\)。
   2. 由 \(a_{i+1}\ge a_i\) 得 \(b_{i+1}=a_{i+1}+i\ge a_i+i=b_i+1>b_i\)，所以 \(b\) 严格递增。
   3. 反向令 \(a_i=b_i-(i-1)\) 即可还原，说明这是一一对应（双射）。于是两类对象个数相等，后者显然是 \(\dbinom{n+k-1}{n}\)。

3. 用以下两种方式之一，给出 \(n\) 分成任意份数的组合（composition）个数的封闭公式（不含求和号）：

   1. 利用 \(n\) 分成给定份数的组合个数公式；
   2. 对 \(n\) 作归纳。
   解题思路答案是 \(2^{\,n-1}\)。\(n\) 分成恰好 \(k\) 份的组合数是 \(\dbinom{n-1}{k-1}\)（隔板法：在 \(n\) 个单位间的 \(n-1\) 个缝里插 \(k-1\) 块板）。
   1. (a) 对份数 \(k\) 从 \(1\) 到 \(n\) 求和：\(\displaystyle\sum_{k=1}^{n}\binom{n-1}{k-1}=\sum_{j=0}^{n-1}\binom{n-1}{j}=2^{\,n-1}\)（用二项式定理，即 \(n-1\) 个缝每个“插或不插”各 \(2\) 种）。
   2. (b) 归纳：把 \(n\) 写成组合时，最后一个单位“接在上一份末尾”或“另起一份”，每加一个单位选择数翻倍，故由 \(n-1\) 到 \(n\) 个数乘 \(2\)。

4. \(n\) 分成任意份数的全部弱组合（weak composition）的个数，有封闭公式吗？

   解题思路注意弱组合允许出现值为 \(0\) 的份。先问：份数是否有上限？
   1. 弱组合允许任意多个 \(0\)。例如 \(n=3\) 可写成 \((3),(3,0),(3,0,0),\dots\) 无穷多种。
   2. 所以全部弱组合有无穷多个，不存在有限封闭公式。结论：没有。

5. 我们要把 \(12\) 个孩子分成四个游戏小组。但这些孩子里有两对兄弟姐妹，我们不希望把兄弟姐妹分到不同组。共有多少种分法？

   解题思路“不拆开”意味着每一对兄弟姐妹应被当作一个不可分割的整体来处理。
   1. 把每对兄弟姐妹“黏成一块”，于是要安置的对象从 \(12\) 个变成 \(10\) 个（\(8\) 个单人 + \(2\) 个绑定对）。
   2. 把这 \(10\) 个对象分成四个非空小组。若小组之间不加区分，分法数为第二类斯特林数 \(S(10,4)\)。

6. \(50\) 分成四个奇数份的组合个数是多少？

   解题思路用“奇数 = \(2c+1\)”的换元把奇数约束去掉，转化为弱组合（隔板法）。
   1. 设四份为 \(a_i=2c_i+1\)（\(c_i\ge0\)）。代入 \(a_1+a_2+a_3+a_4=50\) 得 \(2(c_1+c_2+c_3+c_4)+4=50\)，即 \(c_1+c_2+c_3+c_4=23\)。
   2. 这是 \(23\) 分成四个弱组合（份可为 \(0\)），由隔板法为 \(\dbinom{23+3}{3}=\dbinom{26}{3}\)。

7. 我们要把 \(20\) 千美元的奖金分发给六名工人。其中三名工人的合同规定他们每人至少得 \(2\) 千美元，其余每名工人每人至少得 \(1\) 千美元。如果任何一笔奖金都必须是 \(1000\) 的倍数，那么有多少种分法？

   解题思路以“千美元”为单位，先发掉每人的最低保证额，剩余的钱再自由分配（允许为 \(0\)）。
   1. 单位换成千：总额 \(20\)，三人 \(x_1,x_2,x_3\ge2\)，三人 \(x_4,x_5,x_6\ge1\)。
   2. 先扣除最低额 \(2\times3+1\times3=9\)，剩 \(20-9=11\) 在六人间自由分配（每人 \(\ge0\)）。
   3. 即 \(11\) 分成六个弱组合，由隔板法为 \(\dbinom{11+5}{5}=\dbinom{16}{5}\)。

8. \(10\) 分成四个弱组合、且每份都小于九（即 \(\le 8\)）的个数是多少？

   解题思路“每份有上界”用容斥原理：先不管上界数总数，再减去“某份过大”的坏情形。
   1. 无上界时 \(10\) 分四弱组合共 \(\dbinom{13}{3}\) 个。
   2. 设某一份 \(\ge9\)，把该份减去 \(9\)，余 \(1\) 分四弱组合得 \(\dbinom{4}{3}\)；这样的“坏份”可在 \(4\) 个位置出现，故减去 \(4\dbinom{4}{3}\)。
   3. 两份同时 \(\ge9\) 不可能（已超 \(10\)），无需再加回。最终 \(\dbinom{13}{3}-4\dbinom{4}{3}\)。

9. 从 \([n]\) 到 \([n]\) 的单调函数有多少个？称函数为单调，若 \(x

   解题思路单调（非降）函数完全由它取出的非降值序列 \(f(1)\le f(2)\le\cdots\le f(n)\) 决定，这正是第 2 题里那种“可重复的非降链”。
   1. 一个非降函数 \([n]\to[n]\) 等同于从 \([n]\) 中取一个长度 \(n\)、可重复、非降的取值串，即 \([n]\) 上的 \(n\) 元多重集。
   2. 由第 2 题结论，个数为 \(\dbinom{n+n-1}{n}=\dbinom{2n-1}{n}\)。

10. \(24\) 分成任意份数、且每份都能被 \(3\) 整除的组合个数是多少？

    解题思路每份是 \(3\) 的倍数，整体除以 \(3\) 即把问题缩小为“\(8\) 分成任意份数的组合”，再用第 3 题的结论。
    1. 设每份 \(=3b_i\)（\(b_i\ge1\)），则 \(\sum 3b_i=24\Rightarrow\sum b_i=8\)，份数随意。
    2. 组合的份数与顺序保持不变，故所求等于 \(8\) 分成任意份数的组合数 \(=2^{\,8-1}=2^{7}=128\)。

11. (a) 证明：对所有正整数 \(x\)，

    \[\tag{2.10}x^{\,n}=\sum_{k=0}^{n}S(n,k)\,(x)_k.\]

    (b) 证明 (a) 的结论对所有实数 \(x\) 都成立，而不仅对正整数。

    解题思路(a) 双计数：\(x^n\) 数从 \([n]\) 到 \([x]\) 的全部函数。(b) 用“两个 \(n\) 次多项式在无穷多点相等则恒等”这一代数事实。
    1. (a) 左边 \(x^n\) = \([n]\to[x]\) 的函数总数。把这些函数按像集大小 \(k\) 分类：先把 \([n]\) 划成 \(k\) 个非空块（\(S(n,k)\) 种），再为这 \(k\) 个块从 \([x]\) 里有序选出 \(k\) 个互不相同的像值（\((x)_k=x(x-1)\cdots(x-k+1)\) 种）。求和即得右边。
    2. (b) (2.10) 两边都是关于 \(x\) 的、次数 \(\le n\) 的多项式，且在无穷多个点（全体正整数）取值相等，故两多项式恒等，对一切实数 \(x\) 成立。

12. （需要线性代数基础）用上一题的结果，对“全体实系数多项式构成的向量空间的基”给出一种解释。

    解题思路(2.10) 表明幂基与下降阶乘基可以互相线性表出，斯特林数正是基变换矩阵的元素。
    1. 普通幂基 \(\{1,x,x^2,\dots\}\) 与下降阶乘基 \(\{(x)_0,(x)_1,(x)_2,\dots\}\) 都是该空间的基。
    2. (2.10) 给出从下降阶乘基到幂基的变换系数即第二类斯特林数 \(S(n,k)\)；其逆变换的系数则是带符号的第一类斯特林数。

13. 我想把集合 \([10]\) 划分成三个块，使得两个块大小为 \(3\)、一个块大小为 \(4\)。我有多少种不同的划分方法？

    解题思路先用多项系数把 \(10\) 个元素分到“三个有区别的位置”，再除掉两个同样大小的块之间的重复计数。
    1. 先有序地选：选大小 \(4\) 的块 \(\dbinom{10}{4}\) 种，再选第一个大小 \(3\) 的块 \(\dbinom{6}{3}\) 种，剩下自动成第二个块，得 \(\dbinom{10}{4}\dbinom{6}{3}\)。
    2. 两个大小为 \(3\) 的块本身不分先后，重复了 \(2!\) 次，故结果为 \(\dfrac{1}{2!}\dbinom{10}{4}\dbinom{6}{3}=\dfrac{10!}{4!\,3!\,3!\cdot 2!}\)。

14. 五个人参加跳远比赛。不存在四人并列或五人并列，但可以有两人并列或三人并列。共有多少种可能的名次排列？

    解题思路一个“带并列的名次”就是把 \([5]\) 分成若干有顺序的非空块（有序集划分），约束是每块大小 \(\le3\)。按块的大小型枚举。
    1. 把 \(5\) 个人按名次分成有序的几组，每组内并列。允许的块大小型（各块 \(\le3\)）有：\(1{+}1{+}1{+}1{+}1\)、\(2{+}1{+}1{+}1\)、\(2{+}2{+}1\)、\(3{+}1{+}1\)、\(3{+}2\)。
    2. 对每种型，先用多项系数分人到各块，再乘以这些块排成名次顺序的方式数（相同大小的块按其位置全排列），把各型结果相加即可。

15. 证明定理 2.18。

    解题思路本题要求回到正文，复述并补全定理 2.18 的证明结构。请先在 2.x 节定位该定理的陈述，弄清条件与结论，再按教材给出的方法（通常是双射或递推）逐步论证。

16. 证明：\(n\) 分成至多 \(k\) 份的分拆个数，等于 \(n\) 分成每份都不超过 \(k\) 的分拆个数。

    解题思路这是分拆共轭（conjugation）的经典应用：把 Ferrers 图沿主对角线翻转，行变列。
    1. 把分拆画成 Ferrers 图后取共轭：原来的“份数”（行数）变成共轭图的“最大份”（首列高度）。
    2. 因此“至多 \(k\) 行”一一对应到“每份 \(\le k\)”，共轭是双射，两类个数相等。

17. \(14\) 分成四个互不相同的份的分拆有多少个？

    解题思路把“互不相同”用一个递减偏移去掉，化成普通的“恰好四份”分拆。
    1. 设 \(a_1>a_2>a_3>a_4\ge1\)。令 \(b_i=a_i-(4-i)\)，即从各份减去 \(3,2,1,0\)，把严格递减放松为非严格递减且各份 \(\ge1\)。
    2. 新和为 \(14-(3+2+1+0)=14-6=8\)，于是所求等于 \(8\) 分成恰好四份的分拆个数，直接枚举即可。

18. 若一个分拆等于它自身的共轭，则称为自共轭（self-conjugate）的。哪些正整数没有自共轭分拆？

    解题思路关键事实：\(n\) 的自共轭分拆与 \(n\) 分成互不相同的奇数份的分拆一一对应（沿对角线的 L 形钩子，每个钩子长度是奇数）。
    1. 于是“\(n\) 无自共轭分拆”等价于“\(n\) 不能写成若干互不相同奇数之和”。
    2. 逐个检验：\(1=1\)、\(3=3\)、\(4=1+3\)、\(5=5\)…… 唯独 \(n=2\) 无法表示（只有奇数 \(1\) 可用且不能重复）。结论：仅 \(n=2\)。

19. 回忆 \(p_k(n)\) 表示 \(n\) 分成至多 \(k\) 份的分拆个数。

    1. 证明：对任意固定的 \(k\)，函数 \(p_k(kn)\) 是 \(n\) 的多项式函数。这个多项式的次数是多少？
    2. 证明：对任意固定的 \(k\) 和任意固定的 \(r
    解题思路用生成函数 \(\prod_{i=1}^{k}\frac{1}{1-q^i}\)，它的分母是 \((1-q^k)\) 的因子型；用部分分式把系数表成关于 \(n\) 的拟多项式（quasi-polynomial），在固定余数类 \(n\bmod k\) 上就是真多项式。
    1. (a) \(p_k(n)\) 的生成函数 \(\sum_n p_k(n)q^n=\prod_{i=1}^k\frac{1}{1-q^i}\)。其极点都是单位根，最高阶极点是 \(q=1\)（\(k\) 重），导致系数主项是 \(n^{k-1}\) 量级。固定余数后系数为多项式，次数 \(=k-1\)。
    2. (b) 同理，把 \(n\) 限制在余数类 \(n\equiv r\pmod k\) 上，拟多项式退化为单一多项式，故 \(p_k(kn+r)\) 是 \(n\) 的多项式。

20. 利用上一题的结果证明：\(p(n)\) 的增长快于任何多项式函数 \(q(n)\)。即证：对任意多项式函数 \(q(n)\)，存在正整数 \(N_q\) 使得

    \[\tag{2.11}p(n)>q(n)\quad\text{对所有 }n>N_q.\]
    解题思路用 \(p(n)\ge p_k(n)\) 作下界：把 \(p_k\) 选成次数足够高的多项式，盖过给定的 \(q\)。
    1. 对任意 \(k\)，显然 \(p(n)\ge p_k(n)\)（限制份数只会减少分拆）。
    2. 由上一题，沿合适的余数类 \(p_k(n)\) 是 \(n\) 的 \(k-1\) 次多项式。取 \(k-1\) 大于 \(\deg q\)，则当 \(n\) 充分大时 \(p_k(n)>q(n)\)，从而 \(p(n)>q(n)\)。

21. 证明命题 2.29。

    解题思路回到正文定位命题 2.29 的陈述，理清其假设与结论，按教材所用方法（双射或生成函数）补全推导。

22. 证明命题 2.31。

    解题思路同上，先在正文找到命题 2.31 的准确陈述，再依其上下文给出的工具完成证明。

23. 若 \(n\) 是五边形数（pentagonal number），且对某正整数 \(a\) 有 \(n=a(3a+1)/2\) 或 \(n=a(3a-1)/2\)，则称 \(a\) 使 \(n\) 成为五边形数。证明：对每个五边形数 \(n\)，只有唯一一个正整数 \(a\) 使 \(n\) 成为五边形数。

    解题思路把两族表达式 \(\frac{a(3a\pm1)}{2}\) 看成 \(a\) 的严格单调递增函数，证明它们取值互不重叠且各自一一对应。
    1. 对固定符号，\(f(a)=\frac{a(3a\pm1)}{2}\) 关于 \(a\ge1\) 严格递增，故同一族里不同 \(a\) 给出不同值。
    2. 再验证两族（\(+1\) 与 \(-1\)）的值集不相交（比较相邻取值的大小关系），即可断定能产生 \(n\) 的 \(a\) 唯一。

24. 整数分拆 \(p\) 的 Durfee 方块是能放进 \(p\) 的 Ferrers 图西北角的最大正方形（见图 2.15）。设 \(p\) 的 Durfee 方块边长为 \(k\)。我们如下定义 \(p\) 的逐次秩（successive ranks） \(r_1,r_2,\dots,r_k\)：\(r_i\) 是 Ferrers 图第 \(i\) 行与第 \(i\) 列的差，因此有时逐次秩可能为负。例如图 2.15 所示分拆的逐次秩为 \(1,0,2\)。证明：\(n\) 分成互不相同的份的分拆个数，等于 \(2n\) 的、每个逐次秩都等于 \(1\) 的分拆个数。

    解题思路用 Durfee 方块把分拆拆成“方块 + 右臂 + 下腿”三部分，构造从一边到另一边的双射，让“份互不相同”恰好对应“逐次秩 \(=1\)”。
    1. 逐次秩 \(r_i=(\text{第 }i\text{ 行长})-(\text{第 }i\text{ 列高})\)。要求所有 \(r_i=1\) 即每一行比对应列恰多一格。
    2. 设法把 \(n\) 的一个相异分拆“加倍并错位”地嵌入 \(2n\) 的图中，使每个钩子满足该秩条件；逆映射把多出的一格还原，验证为双射。

25. 在一群人中，每个人写下在场的、自己认识的其他人的数目。（假设若 \(A\) 认识 \(B\)，则 \(B\) 也认识 \(A\)。）

    1. 证明：所有写下的数之和是偶数。
    2. 把写下的数按非增顺序排列，得到某个整数 \(m\) 的 \(2m\) 的一个分拆 \(p\)。\(p\) 的第一个逐次秩 \(r_1\) 能否为非负？
    3. 能否出现 \(r_1+r_2\ge-1\)？（假设 \(r_2\) 有定义，即 \(p\) 的 Durfee 方块边长至少为 \(2\)。）
    解题思路(a) 是图论的握手引理（handshake lemma）：度数之和等于边数的两倍。(b)(c) 把“度数序列”看成分拆并用 Durfee 方块分析其逐次秩上界。
    1. (a) 每段“认识”关系（一条边）恰好给两端各贡献 \(1\)，故所有写下的数之和 \(=2\times(\text{相识对数})\)，必为偶数。
    2. (b)(c) 把度数序列画成 Ferrers 图，分析第 \(i\) 行（某人度数）与第 \(i\) 列的关系；由简单图度数不能超过 \(n-1\) 推出 \(r_1\) 必为负，进而限制 \(r_1+r_2\) 的取值。

26. 证明：若 \(n\) 是奇数，则第三份为 \(2\) 的 \(n\) 的分拆不可能是自共轭的。

    解题思路用第 18 题的事实：自共轭分拆对应于互不相同奇数份的分拆；再分析“第三份为 \(2\)”对前三份（递减排列）的强制条件。
    1. 分拆按非增排列，第三份为 \(2\) 意味着前两份 \(\ge2\)，而后面各份 \(\le2\)。
    2. 结合自共轭等价于互异奇数份，分析在该形状约束下钩子长度的奇偶与个数，导出 \(n\) 必为偶数，与 \(n\) 奇矛盾。

27. 把数字 \(1,1,2,2,3,4,5\) 排成一行，使得相同的数字不相邻，共有多少种排法？

    解题思路“某些元素不相邻”用容斥原理：定义坏事件“两个 \(1\) 相邻”“两个 \(2\) 相邻”，从总排列里减去坏的、加回重复减的。
    1. 七个数字（含两组重复）的全排列共 \(\dfrac{7!}{2!\,2!}\) 种。
    2. 设 \(A=\)“两个 \(1\) 相邻”，\(B=\)“两个 \(2\) 相邻”。把相邻的一对捆成一块算：\(|A|=\dfrac{6!}{2!}\)，\(|B|=\dfrac{6!}{2!}\)，\(|A\cap B|=5!\)。
    3. 所求 \(=\dfrac{7!}{2!2!}-2\cdot\dfrac{6!}{2!}+5!\)。

28. 回到例 2.36。如果要求每个子组都至少包含一名会说当地人语言的人，那么把游客分成子组的方法有多少种？

    解题思路“每个子组都含某类人”是经典的容斥或带限制的集划分问题；先回到例 2.36 弄清游客总数与“会当地语言”的人数，再扣除“存在子组全是不会的人”的情形。

29. 不超过 \(1000\) 且与 \(7\) 和 \(8\) 都互素的正整数有多少个？

    解题思路与 \(7\) 互素即不被 \(7\) 整除；与 \(8\) 互素即不被 \(2\) 整除。用容斥原理从 \(1000\) 中减去被 \(2\) 或被 \(7\) 整除的个数。
    1. 被 \(2\) 整除：\(\lfloor1000/2\rfloor=500\)；被 \(7\) 整除：\(\lfloor1000/7\rfloor=142\)；同时被 \(14\) 整除：\(\lfloor1000/14\rfloor=71\)。
    2. 由容斥，被 \(2\) 或 \(7\) 整除的有 \(500+142-71=571\) 个。
    3. 所求 \(=1000-571=429\)。

30. 一家大公司（指至少有三名员工的公司）的员工总共会说四种语言。对任意三名员工，都至少有一种语言是他们三人都会的。但没有一种语言是全体员工都会的。证明：每名员工都至少会三种语言。并构造一个满足上述条件的例子。

    解题思路用反证法：假设某员工只会 \(\le2\) 种语言，配合“没有全员通用语言”推出每种语言都有人不会，再从这些“不会的人”里挑三人破坏“任意三人有共同语言”。
    1. 因没有全员语言，每种语言 \(L\) 至少有一名员工 \(x_L\) 不会。
    2. 若某员工只会两种语言，则他对另外两种语言都“不会”；连同对应的 \(x_L\) 构造出三人，使这三人没有共同语言，矛盾。故每人至少会三种。
    3. 构造例子：让四种语言两两缺人即可，例如每名员工恰好不会一种语言（四类各一人）。

31. 为定理 2.38 证明的 (b) 部分，找出一个不涉及计算的替代论证。

    解题思路回到正文 2.38 的 (b) 部分，理解它在用代数式凑出的等式背后的组合意义；用一个双射或直接计数（“两边在数同一类对象”）来代替原来的代数计算。

32. 设 \(D(n)\) 为例 2.49 定义的错位排列（derangement）个数。求和式

    \[\sum_{i=0}^{n}\binom{n}{i}D(i)\]

    的封闭公式。可令 \(D(0)=1\)。

    解题思路组合解释：\([n]\) 的每个排列都可按“恰好有哪些点是不动点”来分类，剩下的部分是一个错位排列。
    1. 给定一个 \([n]\) 的排列，设其不动点构成的集合大小为 \(n-i\)；先从 \(n\) 个位置里选出这 \(n-i\) 个不动点（\(\dbinom{n}{n-i}=\dbinom{n}{i}\) 种），其余 \(i\) 个元素做错位排列（\(D(i)\) 种）。
    2. 对所有可能的 \(i\) 求和，恰好把全体排列数清一遍，故 \(\displaystyle\sum_{i=0}^{n}\binom{n}{i}D(i)=n!\)。

33. 设 \(A_1,A_2,\dots,A_n\) 为有限集合。引入记号

    \[D_k=\sum_{(i_1,i_2,\dots,i_k)}\bigl|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}\bigr|,\]

    其中 \((i_1,i_2,\dots,i_k)\) 取遍 \([n]\) 的全部 \(k\) 元子集。换言之，\(D_k\) 是这些集合所有 \(k\) 重交集大小之和。证明：恰好属于 \(A_i\) 中 \(n-2\) 个的元素个数为

    \[B_{n-2}=D_{n-2}-(n-1)D_{n-1}+\binom{n}{2}D_n.\]
    解题思路这是容斥原理“恰好属于若干个”版本的特例。核心引理：一个恰属于 \(m\) 个集合的元素，在 \(D_k\) 中被计入 \(\dbinom{m}{k}\) 次。
    1. 一个恰属于 \(m\) 个集合的元素，对 \(D_k\) 的贡献是 \(\dbinom{m}{k}\)（在该元素所在的 \(m\) 个集合里任选 \(k\) 个交集）。
    2. 验证右端的系数组合 \(\dbinom{m}{n-2}-(n-1)\dbinom{m}{n-1}+\dbinom{n}{2}\dbinom{m}{n}\) 当 \(m=n-2\) 时为 \(1\)，当 \(m=n-1,n\) 时为 \(0\)，从而只数出“恰属于 \(n-2\) 个”的元素。

34. 沿用上题的记号，证明：恰好属于 \(A_i\) 中 \(n-3\) 个的元素个数为

    \[B_{n-3}=D_{n-3}-(n-2)D_{n-2}+\binom{n-1}{2}D_{n-1}-\binom{n}{3}D_n.\]
    解题思路与第 33 题完全同一套机制，只是把“恰好 \(n-3\) 个”代入。仍用引理“恰属 \(m\) 个者在 \(D_k\) 中计 \(\dbinom{m}{k}\) 次”，验证右端系数对 \(m=n-3\) 给 \(1\)，对 \(m=n-2,n-1,n\) 给 \(0\)。

35. 对某个 \(k\in[n]\)，叙述并证明恰好属于 \(k\) 个集合 \(A_i\) 的元素个数 \(B_k\) 的一般公式。

    解题思路把前两题推广成统一公式，这正是容斥原理的“恰好 \(k\) 个”形式。
    1. 一般公式为 \(\displaystyle B_k=\sum_{j=k}^{n}(-1)^{\,j-k}\binom{j}{k}D_j\)。
    2. 证明仍靠引理：恰属 \(m\) 个的元素对该和的总贡献是 \(\sum_{j}(-1)^{j-k}\binom{j}{k}\binom{m}{j}\)，用组合恒等式化简后，当 \(m=k\) 为 \(1\)、否则为 \(0\)。

36. 给出一个无限集合族 \(\mathcal{F}\) 的例子，使得 \(\mathcal{F}\) 的每个无限子族的交集为空，而每个有限子族的交集为无限集。试找出至少两种解法。

    解题思路要的是“有限交无穷、无限交为空”的对象。最常见的构造是逐渐缩小的尾集：取 \(A_i=\{i,i+1,i+2,\dots\}\)。
    1. 解法一（尾集）：令 \(A_i=\{n\in\mathbb{Z}^+:n\ge i\}\)。任意有限个 \(A_{i_1},\dots,A_{i_m}\) 的交 \(=A_{\max i_j}\)，仍无限；但所有 \(A_i\) 的交（任何无限子族）为空，因为没有正整数大于等于所有的 \(i\)。
    2. 解法二：在 \(\mathbb{N}\) 上令 \(A_i=\mathbb{N}\setminus\{i\}\)（去掉一个点）。任意有限族交集只去掉有限个点，仍无限；任意无限族交集去掉无限个点……需调整使其为空，例如令 \(A_i=\mathbb{N}\setminus\{0,1,\dots,i\}\)，本质同尾集。可再给出区间型 \(A_i=[i,\infty)\subset\mathbb{R}\) 中取整数等变体。

返回 全书目录