systematically 数清每一种可能
计数问题看似只是"数数"，但在复杂场景下，直觉往往不可靠。乘法原理和加法原理是所有计数技术的基石。
如果完成一件事需要 k 个步骤，第1步有 n₁ 种方法，第2步有 n₂ 种方法，...，第 k 步有 nₖ 种方法，则完成这件事共有 n₁ × n₂ × ··· × nₖ 种方法。
想象你在构建一个"选择树"——每一步的选择都会让分支数量乘以该步的选项数。乘法原理的本质是分步选择的笛卡尔积。
如果完成一件事有 k 类不同的方法，第1类有 n₁ 种，第2类有 n₂ 种，...，且各类方法之间互不重叠，则完成这件事共有 n₁ + n₂ + ··· + nₖ 种方法。
乘法对应"AND"（且）——你做完了第一步并且做完了第二步，才算完成。 加法对应"OR"（或）——你可以用第一类方法或者第二类方法，都算完成。一句话：分步用乘法，分类用加法。
排列（Permutation）关注的是"顺序 matters"的选择。从 n 个不同元素中取出 k 个排成一列，称为从 n 取 k 的排列。
当 k = n 时，称为全排列，P(n, n) = n!。
如果 n 个元素中有重复，其中有 n₁ 个相同，n₂ 个相同，...，则不同的排列数为：
密码强度分析：一个8位密码，每位可以是大写字母（26种）、小写字母（26种）、数字（10种）或特殊符号（10种），共72种选择。根据乘法原理，总的可能密码数（密钥空间）为 72⁸ ≈ 7.2 × 10¹⁴。如果黑客每秒尝试10亿次，穷举需要约8天。加入第9位后，密钥空间变为 72⁹ ≈ 5.2 × 10¹⁶，穷举需要约1.6年。每增加一位，安全性呈指数级提升。
网格路径问题：在一个 m×n 的网格中，从左上角到右下角只能向右或向下走，共有多少条不同路径？这是一个组合问题（等价于在 m+n 步中选择 m 步向下），答案为 C(m+n, m)。在路由算法中，理解路径数量有助于评估网络冗余度和负载均衡策略的复杂度。
组合（Combination）关注的是"顺序不重要"的选择。从 n 个不同元素中取出 k 个作为一个集合，称为从 n 取 k 的组合。
组合数也读作"n 选 k"或"二项式系数"。它出现在 (a + b)ⁿ 的展开式中：
| 性质 | 公式 | 直觉 |
|---|---|---|
| 对称性 | C(n, k) = C(n, n-k) | 选 k 个留下，等价于选 n-k 个排除 |
| 边界值 | C(n, 0) = C(n, n) = 1 | 什么都不选或全选，都只有1种方式 |
| 递推（帕斯卡） | C(n, k) = C(n-1, k-1) + C(n-1, k) | 第 n 个元素选或不选 |
| 总和 | Σₖ₌₀ⁿ C(n, k) = 2ⁿ | n 个元素的子集总数 |
排列 = 先选（组合）再排。从 n 个元素中选 k 个并排列，可以先 C(n, k) 选出 k 个，再 k! 进行全排列。因此 P(n, k) = C(n, k) × k!。这个关系揭示了"顺序是否重要"是排列与组合的根本区别。
基因型组合：人类有23对染色体，每对中的一条来自父亲，一条来自母亲。仅考虑独立分配（不计算交叉互换），一个个体可能产生的不同配子数为 2²³ ≈ 840万。两个个体结合后，后代可能的基因组合数更为惊人。理解组合原理是群体遗传学和育种工程的基础。
当多个集合有重叠时，直接相加会重复计算交集部分。容斥原理（Inclusion-Exclusion Principle）系统地修正了这种重复计数。
一般地，对于 n 个集合：
容斥原理的符号交替出现：加单集、减两两交集、加三个交集、减四个交集……这是因为每增加一层交集，重复计数的问题就反转一次。想象三个重叠的圆圈：先加三个圆，两两重叠区被加了两次所以各减一次，但中心三区交集被加了三次又减了三次，最后需要再加一次。
生日问题是概率论中最著名的反直觉问题之一：一个房间中至少需要多少人，才能使至少两人生日相同的概率超过50%？
答案是 23 人——远小于大多数人的直觉（通常猜测100以上）。
计算"至少两人生日相同"的概率，用补集更方便：先算"所有人生日都不同"的概率。
关键在于比较的对数。23个人之间可以形成 C(23, 2) = 253 对比较。每一对都有 1/365 的概率生日相同。虽然单一对的概率很小，但253次"尝试"累积起来的概率就很可观了。这类似于彩票：买一张中奖概率极低，但买大量不同号码后中奖概率显著上升。
密码学与数据结构：生日问题的原理直接应用于哈希碰撞分析。一个64位的哈希函数有 2⁶⁴ 种可能输出，但根据生日悖论，大约只需要 2³² ≈ 40亿 次随机输入就有较大概率发生碰撞。这就是为什么 SHA-1（160位）被认为不够安全——生日攻击将复杂度从 2¹⁶⁰ 降低到约 2⁸⁰。
某系统要求密码为8位，每位可以是数字（0-9）或小写字母（a-z）。
(a) 共有多少种可能的密码？
(b) 若要求至少包含1个字母，有多少种密码？
每位有 10 + 26 = 36 种选择，共8位。
根据乘法原理：总数 = 36⁸ = 2,821,109,907,456 ≈ 2.82 × 10¹²
用补集：总数 - 全数字密码数
全数字密码数 = 10⁸ = 100,000,000
至少1个字母 = 36⁸ - 10⁸ = 2,821,109,907,456 - 100,000,000 = 2,821,009,907,456
从12名员工中选出5人组成项目委员会。
(a) 有多少种不同的选法？
(b) 若必须包含特定的2名资深员工，有多少种选法？
(c) 若2名资深员工不能同时入选，有多少种选法？
从12人中选5人，顺序不重要，用组合：
C(12, 5) = 12! / (5! × 7!) = (12×11×10×9×8) / (5×4×3×2×1) = 95040 / 120 = 792
这2人已确定入选，还需从剩余10人中选3人：
C(10, 3) = 10! / (3! × 7!) = (10×9×8) / 6 = 120
用容斥原理或直接分类：
方法一：总数 - 两人同时入选数 = 792 - C(10, 3) = 792 - 120 = 672
方法二：只选A不选B + 只选B不选A + 两人都不选 = C(10,4) + C(10,4) + C(10,5) = 210 + 210 + 252 = 672
计算30人中至少两人生日相同的概率。假设一年365天，生日均匀分布。
P(全不同) = (365/365) × (364/365) × ··· × (336/365)
= P(365, 30) / 365³⁰ = 365! / [(365-30)! × 365³⁰]
P(全不同) ≈ 0.2937
P(至少一对相同) = 1 - 0.2937 = 0.7063 ≈ 70.6%
一个哈希函数输出32位（约43亿种可能）。大约需要多少次随机输入，才能使碰撞概率超过50%？
这等价于"生日问题"，N = 2³² ≈ 4.29 × 10⁹。
P(无碰撞) = N! / [(N-n)! · Nⁿ] ≈ exp[-n(n-1)/(2N)] （近似公式）
令 P(无碰撞) ≈ 0.5：
exp[-n²/(2N)] ≈ 0.5
-n²/(2N) ≈ ln(0.5) = -0.693
n ≈ √(2N × 0.693) ≈ √N × 1.177
n ≈ √(4.29 × 10⁹) × 1.177 ≈ 65536 × 1.177 ≈ 77,100
也就是说，仅需约 77,000 次随机输入，碰撞概率就超过50%！
以下 MATLAB 代码演示排列组合计算和生日问题的模拟验证。