乘积规则 × 求和规则 +
The Product Rule & The Sum Rule|P₁ × P₂ × ⋯ × Pₙ| = |P₁|·|P₂|⋯|Pₙ|——每天早饭 4 选 1、午饭 3 选 1、晚饭 5 选 1，一天吃法共 4·3·5 = 60 种。
集合不交时：|A₁ ∪ A₂ ∪ ⋯ ∪ Aₙ| = |A₁|+|A₂|+⋯+|Aₙ|——Lisa 有 20 个暴躁日、40 个恼火日、60 个坏脾气日，能不爽的日子共 20+40+60 = 120 天。重叠的场合要等 15.9 容斥。
真正的计数题几乎都要两个规则连用：某系统密码为 6–8 位，首位必须字母（52 选 1），其余位字母或数字（62 选 1）。总密码数 = 三个互斥长度类之和：
同样的套路换个皮肤就是习题里的车牌：普通牌"3 字母 + 3 数字"、个性牌"5 字母"、大佬牌"2 个任意字符"——三选一求和，每一项再乘积拆开。下面亲手拨一拨：
广义乘积规则：后一项依赖前一项
The Generalized Product Rule长度 k 的序列集 S：若第 1 项有 n₁ 种、每个第 1 项下第 2 项有 n₂ 种……则 |S| = n₁·n₂⋯nₖ。三项奖发给不同的人：n·(n−1)·(n−2)——这就是阶乘的出身。
缺陷钞票（15.3.1）：8 位序列号中出现重复数字即为"缺陷"。全部序列号 10⁸ 张；数字互不相同的只有 10·9·8·7·6·5·4·3 = 10!/2! = 1,814,400 张——仅 1.8144%。掏出钱包看看，你兜里几乎必然躺着"缺陷钞票"。
棋盘放子（15.3.2）：兵、马、象各占一行一列互不冲突——行 8·7·6、列同样 8·7·6，共 (8·7·6)² = 112,896 种。行和列互不干扰，各自是一轮广义乘积。
除法规则：数耳朵再除以二
The Division Rulef : A → B 是 k-to-1（每个 B 恰被 k 个 A 映射），则 |A| = k·|B|。数耳朵（2 对 1）除以二得人数；数手指（10 对 1）除以十。
两枚相同的车（15.4.1）：把配置描述成序列 (r₁,c₁,r₂,c₂) 有 (8·7)² 种——但每个真实摆法被数了 2 次（先说哪枚车都一样），答案 (8·7)²/2 = 1,568。
圆桌骑士（15.4.2）：n 个骑士围圆桌就座，旋转不算新排法——n 个座位序列对应同一 arrangement，映射 n-to-1，所以圆桌排法 = n!/n = (n−1)!。第 17 章概率里它还会回来。
数子集：n 选 k 登场
Counting Subsets100 本书中挑 5 本度假带上、52 张牌发 13 张桥牌、14 种配料选 5 个做披萨——同一个问题的三件马甲：
n! 个排列里，前 k 个元素的每一种组合被重复 k!·(n−k)! 次（前段任意排 × 后段任意排），映射 k!(n−k)!-to-1，所以 ( n / k ) = n! / (k!(n−k)!)。
推论 15.5.2：恰含 k 个 1 的 n-bit 串有 ( n / k ) 个——子集与比特串的双射（第 4 章埋的线，这里收口）。推论 15.5.3：k 种口味的甜甜圈选 n 个，共 ( (n+k−1) / n ) 种——"隔板法"预告，第 16 章生成函数见。
重复序列与 Bookkeeper 法则
Sequences with Repetitions把 n 元集合切成 (k₁,…,kₘ) 大小的 m 段：多项式系数 ( n / (k₁,…,kₘ) ) = n!/(k₁!⋯kₘ!)。它最著名的应用是数"字母可以重复的排列"——BOOKKEEPER 有 1 个 B、2 个 O、2 个 K、3 个 E、1 个 P、1 个 R：
同样的公式反过来就是二项式定理：(a+b)⁴ 完全展开的 16 项里，恰含 k 个 b 的项有 ( 4 / k ) 个，所以 bᵏ 的系数就是 ( 4 / k )。多项式定理（15.6.5）是它的 m 元版——书中建议：记住推理，忘掉那行吓人的公式。
计数实习：扑克手牌
Counting Practice: Poker Hands五张抽牌共 ( 52 / 5 ) = 2,598,960 种手牌。数"带特殊性质的牌型"的通用套路：把手牌双射到一个易数的序列，再上广义乘积——每一步都要问"这真是双射吗？"两对牌会替你记住这个教训。
鸽笼原理：挤一挤，必然撞衫
The Pigeonhole Principle鸽子比笼子多，则必有两只鸽子同笼。形式版（15.8.1）：|A| > |B| 则任何全函数 f : A → B 必把两个不同元素映到同一点——它就是映射规则单射情形的逆否命题。加强版（15.8.2）：|A| > k·|B| 则有 k+1 只鸽子同笼。
黑屋抽袜：3 种颜色的袜子，抽 4 只必有同色一对（3 个笼子装 4 只袜子）。波士顿怪谈：50 万非秃头市民、每人头发 ≤20 万根，2·|B| < |A| → 至少 3 个人发数完全相同——不知道是谁，但一定存在（非构造性证明）。以及那个著名的炸弹：90 个 25 位数，必有两个不同子集的和相等，因为 2⁹⁰ ≈ 1.24×10²⁷ 个子集远多于 90·10²⁵ 种可能的和。
用鸽笼原理解题的三要素：指明鸽子 A、笼子 B、分配规则 f。下面四案，你来当裁判：
15.8.4纸牌魔术：不需要读心，只需要计数
助手把 5 张牌亮出 4 张，魔术师就能报出第 5 张。信息论帐：5 选 4 的顺序有 4! = 24 种，而暗牌有 48 种可能——不够！但助手还能选藏哪张：C(52,5) 个五张集合各连着 5·4! = 120 个四张序列，右边的序列节点只 52·51·50·49 个——左边度数 120、右边度数 48，按定理 12.5.6 这个二部图必有匹配（第 12 章 Hall 定理的还乡）：理论上 124 张牌的魔术都办得到。
实际操作方案（15.8.5）更妙：五张牌必有同花两张（鸽笼！4 花色 5 张牌）；同花两张在 13 个点数的环上顺时针距离必有一个 ≤6——先亮的那张报告花色，顺时针跳数报告点数差；剩下三张按约定全序分大中小，6 种排列恰好编码 1–6。
容斥原理：数重了就减回去，减多了再加回来
Inclusion-Exclusion数学系 60 人、EECS 系 200 人、物理系 40 人，跨系修课的重叠让 Sum Rule 失效。两集版：|S₁∪S₂| = |S₁|+|S₂|−|S₁∩S₂|；三集版要再"容"回三集交集：
书中 42/04/60 连续问：0–9 的排列中含 42 或 04 或 60 连续的个数——把"60"打包成一个字符变成 9!，容斥逐层打包：3·9! − 3·8! + 7!。n 集通式（Rule 15.9.1）：单集之和 − 两两交集之和 + 三三交集之和 − ⋯ 交替到底。副产品：欧拉函数 φ(n) = n·∏(1−1/pᵢ) 的显式公式（第 9 章 RSA 用过）就是容斥数出来的。
组合证明：不用代数的代数恒等式
Combinatorial Proofs要证一个关于计数的恒等式，最漂亮的办法是数同一个东西两次：找一个集合，用两种方式数它，两边自然相等。不用展开、不用归纳，一个双射顶 ten 行代数。三连证：
习题实战
Practice Problems, Playable一道原书 Practice Problem 做成解题器（牌照实验室则是习题 15.5 的互动版）。
终局自测
Final Check八题，覆盖 15.2–15.10。
彩蛋与课后挑战
Easter Eggs & ProblemsStirling 近似：n! 的渐近身材（15.3.3）
排列数为什么总以阶乘现身？n! ~ √(2πn)(n/e)ⁿ——上一章的 ~ 记号在这领工资。50! ≈ 3.04×10⁶⁴，粗算用 Stirling 一两秒出数量级。
$500 悬而未决：Erdős 的子集和猜想（15.8.2 侧栏）
2 的幂 {1,2,4,8,16} 所有子集和互不相同——太平凡。但 {6,9,11,12,13} 也全体互不相同，而且最大数更小！Erdős 1931 年猜想：这种集合的最大元素必须 ≥ c·2ⁿ。悬赏 $500，至今未解。
124 张牌的魔术是真实可能的（15.8.5）
匹配的存在性由 Hall 定理担保（度数 120 vs 48，度数受限图必有匹配——定理 12.5.6），所以只要牌堆 ≤124 张，"亮 4 报 1"在原理上无懈可击。难点是脑内记住 2,598,960 条匹配边——同花+环跳+三牌排列的 15.8.5 方案就是给这套匹配找的一个"心算可执行"的子程序。四张牌版本被鸽笼判死：⌈C(52,4)/(52·51·50)⌉ = 3，亮 3 张至少对应 3 种第四张。
课后挑战（均出自原书习题）
- 15.2 第 16 章练习题答题方式总数（4 道判断 × 4 选 1 × 15..20 的整数——Sum×Product 连击）。
- 15.5 车牌：用 ∪ 和 × 写出 L 的集合表达式，再算 |L|（互动①就是它）。
- 15.38(d) n+1 个数选自 {1,…,2n}，必有两数相邻（从而互素）——鸽笼 + 相邻配对。
- 15.10 组合证明：( n / k ) = ( n / n−k )（T 恤论证）；Pascal 恒等式（Bob 入队/不入队）；Σ(n/r)(2n/n−r) = (3n/n)（红黑牌，定理 15.10.2）。