知识焦点
先建立概念地图
- stars and bars
- balls and bins
- inclusion-exclusion
- combinatorial proof
- Pascal's Identity
- binomial coefficients
- 隔板法
- 容斥原理
CS70 · 讨论课 06b
CS 70 讨论课 06B，涵盖三类组合计数问题：(1) 农夫市场——用隔板法（stars and bars）计算在多种水果中选取 k 个的方案数，并加入“至少两种水果”的约束；(2) 容斥原理——计算小于 100 且与 100 互质的正整数个数；(3) CS70 音乐剧——通过组合论证（combinatorial argument）证明四个二项式系数恒等式，包括分组选导演、帕斯卡恒等式、先选剧组再选主角，以及推广到选 j 个主角的一般情形。
知识焦点
建议顺序
先完整作答，再按需展开提示；最后才展开官方参考解答并逐步核对证明与计算。
本地来源
题面与解答均由本地一手资料整理：discussion/dis06b.pdf、solutions/discussion/dis06b-sol.pdf
本地一手资料完整提取 · 讨论课
本节按本地一手资料完整整理，共 3 道大题。本地官方解答已完整收录并默认折叠；建议先独立完成，再逐题核对推导。
discussion/dis06b.pdf、solutions/discussion/dis06b-sol.pdf（对应 Note 10）假设你想从农夫市场买 \(k\) 个物品。在下列假设下，分别计算有多少种不同的选法：
(a) 市场上有南瓜（pumpkins）和苹果（apples）。
(b) 市场上有南瓜、苹果、橙子（oranges）和梨（pears）。
(c) 市场上有 \(n\) 种水果，且你希望最终至少买到两种不同类型的水果。
这是经典的"球与盒"（balls and bins，又称"星与条"stars and bars）模型：把 \(k\) 个相同的物品看成 \(k\) 颗星，把不同水果种类看成盒，用隔板（bar）来分隔。
对于 (c)，先算无任何限制时的总方案数，再剔除"只含那一种水果"的情形。注意这里的"至少两种"意味着要减去 \(n\) 种单一水果的选法。
这是一道经典的"球与盒"（balls and bars，又称"星与条"stars and bars）问题。
(a) 共有 \(k+1\) 种选法。我们可以取 0 个南瓜和 \(k\) 个苹果，或 1 个南瓜和 \(k-1\) 个苹果，……，一直到 \(k\) 个南瓜和 0 个苹果。等价地，这相当于 \(k\) 颗星（物品）和 1 条隔板（bar），把物品分到 2 个盒（水果种类）中，因此方案数为
\[ \binom{k+1}{1} = \binom{k+1}{k}. \]
(b) 共有 \(\displaystyle\binom{k+3}{3}\) 种选法。此时有 \(k\) 颗星和 3 条隔板（对应 4 种水果）。
(c) 无任何限制时，从 \(n\) 种水果中取 \(k\) 个（允许重复、不计顺序）的方案数为
\[ \binom{n+k-1}{n-1} = \binom{n+k-1}{k}, \]
即 \(k\) 颗星和 \(n-1\) 条隔板。然而这些方案中，有 \(n\) 种只含有单一水果（全部 \(k\) 个都是同一种），不满足"至少两种"的要求，应予剔除。因此最终方案数为
\[ \binom{n+k-1}{n-1} - n = \binom{n+k-1}{k} - n. \]
解答来源：solutions/discussion/dis06b-sol.pdf · 1 · confidence: high
题面来源：discussion/dis06b.pdf · 1 · confidence: high
（对应 Note 10）小于 \(100\) 的正整数中，有多少个与 \(100\) 互质（coprime）？
直接计数"与 \(100\) 互质"较难，考虑反面：先数小于 \(100\) 且不与 \(100\) 互质的正整数。若某数与 \(100\) 不互质，则它必被 \(2\) 或 \(5\) 整除。
用容斥原理处理"\(2\) 的倍数"与"\(5\) 的倍数"这两个集合的并集，注意它们的交集是 \(10\) 的倍数。
考虑其反面：先求小于 \(100\) 且不与 \(100\) 互质的正整数个数。
若某数与 \(100\) 不互质，则它必是 \(2\) 的倍数或 \(5\) 的倍数。统计如下：
\(2\) 的倍数有 \(49\) 个；
\(5\) 的倍数有 \(19\) 个；
同时是 \(2\) 和 \(5\) 的倍数（即 \(10\) 的倍数）有 \(9\) 个。
由容斥原理，小于 \(100\) 且不与 \(100\) 互质的正整数共有
\[ 49 + 19 - 9 = 59 \]
个。而小于 \(100\) 的正整数共有 \(99\) 个，因此所求的与 \(100\) 互质的正整数个数为
\[ 99 - 59 = 40. \]
解答来源：solutions/discussion/dis06b-sol.pdf · 1 · confidence: high
题面来源：discussion/dis06b.pdf · 1 · confidence: high
（对应 Note 10）Edward 是前任首席助教（head TA），正在筹备他的最新项目《CS70：音乐剧》（CS70: The Musical）。现在他需要挑选演员（cast）、剧组（crew）和导演团队（directing team）。
(a) 首先，Edward 要为音乐剧挑选导演。共有 \(2n\) 名导演投递了申请。请以此为组合场景，给出下列恒等式的组合论证（combinatorial argument）：
\[ \binom{2n}{2} = 2\binom{n}{2} + n^2. \]
(b) 接着，Edward 要从 \(n\) 人中挑选一个剧组。请以此为组合场景，给出下列恒等式的组合论证（该恒等式称为帕斯卡恒等式，Pascal's Identity）：
\[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. \]
(c) 共有 \(n\) 名演员排在 Edward 办公室门外，都想在剧中获得一个角色（含主角 lead role）。但 Edward 尚未确定要挑选多少人。请以此为组合场景，给出下列恒等式的组合论证：
\[ \sum_{k=1}^{n} k\binom{n}{k} = n 2^{n-1}. \]
(d) 将上一部分推广：请给出下列恒等式的组合论证：
\[ \sum_{k=j}^{n} \binom{n}{k}\binom{k}{j} = 2^{\,n-j}\binom{n}{j}. \]
组合论证的核心是：对同一个组合对象，用两种不同的方式计数，从而得到等式两边。
对于 (a)，把 \(2n\) 名导演分成两组各 \(n\) 人（例如"有经验"与"无经验"），按"两名都来自第一组 / 都来自第二组 / 两组各一人"三种互斥情况计数。对于 (b)，固定考察第一名候选人，按"选他"与"不选他"两种情形拆分。
对于 (c) 与 (d)，场景是：先从 \(n\) 名演员中选一个子集作为剧组，再从剧组中选出主角（(c) 选 1 名主角，(d) 选 \(j\) 名主角）。左式先定剧组规模 \(k\) 再计数；右式先选主角，再对剩余演员决定是否入组。
(a) 考虑从 \(2n\) 名候选人中挑选 \(2\) 名导演。
左式（LHS）：直接从 \(2n\) 人中选 \(2\) 人，方案数为 \(\displaystyle\binom{2n}{2}\)。
右式（RHS）：将 \(2n\) 名导演任意分成两组，每组 \(n\) 人（例如一组为有经验者，另一组为无经验者）。挑选 \(2\) 名导演时，只有以下三种互斥情况：
两人都来自有经验组，方案数 \(\displaystyle\binom{n}{2}\)；
两人都来自无经验组，方案数 \(\displaystyle\binom{n}{2}\)；
有经验组一人、无经验组一人，方案数 \(n^2\)。
这三类互斥且穷尽所有可能，其和即为从 \(2n\) 人中选 \(2\) 人的总方案数。恒等式得证。
(b) 考虑从 \(n\) 名候选人中挑选 \(k\) 名剧组成员。
左式（LHS）：直接从 \(n\) 人中选 \(k\) 人，方案数为 \(\displaystyle\binom{n}{k}\)。
右式（RHS）：换一种方式挑选。Edward 先考察他遇到的第一名候选人，决定是否选他：
若选此人，则还需从剩下 \(n-1\) 人中再选 \(k-1\) 人，方案数 \(\displaystyle\binom{n-1}{k-1}\)；
若不选此人，则需从剩下 \(n-1\) 人中选全部 \(k\) 人，方案数 \(\displaystyle\binom{n-1}{k}\)。
两种情形互不重复（第一种情形下第一名候选人必被选，第二种下必不被选），合起来即为全部选法。恒等式得证。
(c) 场景为：Edward 先从 \(n\) 名演员中选一个子集作为剧组，再从剧组中选出 \(1\) 名主角。
左式（LHS）：先选定剧组规模 \(k\)（\(k\) 从 \(1\) 到 \(n\)），从 \(n\) 人中选 \(k\) 名演员，再从这 \(k\) 名演员中选 \(1\) 名主角（注意 \(\displaystyle k = \binom{k}{1}\)）。对 \(k\) 求和即覆盖所有非空子集，因此该式计数了所有"先选剧组、再选主角"的方案。
右式（RHS）：Edward 先从 \(n\) 人中选 \(1\) 名主角；再对剩余 \(n-1\) 名演员中的每一位，独立决定是否将其纳入剧组。剩余 \(n-1\) 人的所有（可能为空的）子集数为 \(2^{n-1}\)。因此总方案数为 \(n \cdot 2^{n-1}\)。
两种方式计数同一对象，恒等式得证。
(d) 场景为：Edward 先从 \(n\) 名演员中选一个子集作为剧组，再从剧组中选出 \(j\) 名主角（而非 (c) 中的 \(1\) 名）。
左式（LHS）：先选定剧组规模 \(k\)（\(k\) 从 \(j\) 到 \(n\)；若 \(k < j\) 则无法选出 \(j\) 名主角，为非法情形），从 \(n\) 人中选 \(k\) 名演员，再从这 \(k\) 名演员中选 \(j\) 名主角。对 \(k\) 求和即覆盖所有合法子集，因此该式计数了所有"先选剧组、再选 \(j\) 名主角"的方案。
右式（RHS）：Edward 先从 \(n\) 人中选 \(j\) 名主角；再对剩余 \(n-j\) 名演员中的每一位，独立决定是否将其纳入剧组。完成这一决策的方式共有 \(2^{n-j}\) 种。因此总方案数为 \(2^{n-j}\displaystyle\binom{n}{j}\)。
两种方式计数同一对象，恒等式得证。
解答来源：solutions/discussion/dis06b-sol.pdf · 2-3 · confidence: high
题面来源：discussion/dis06b.pdf · 2-3 · confidence: high
discussion/dis06b.pdfsolutions/discussion/dis06b-sol.pdf