元数据卡
- 前置知识：第5章 关系与函数
- 预计时间：45 分钟
- 核心难度：入门
- 完成标志：掌握加法原理和乘法原理，能区分排列和组合，计算简单组合数
你的进度
你从离散数学的塔楼走出，穿过一段连廊，进入第二座塔——组合塔。这座塔里没有石门，全是巨大的算盘。馆长站在第一面算盘前，拨动了几颗珠子："只有几颗珠子，但能摆出多少种状态？"
你的任务
给定 10 个数字，能组成多少个不同的 4 位数密码？一个 8 人团队选 3 个人出差的方案有多少种？排列组合解决的本质是同一个问题：计数。你在软件中遇到的每一种可能状态空间的规模、每一个搜索空间的大小、每一种测试覆盖率的计算——都依赖于这里。
本章分层
- 必读：加法/乘法原理，排列，组合
- 选读：鸽巢原理，二项式定理
破局 · 溯源
你在设计一个权限系统：五种角色、二十个资源、三种操作权限（读、写、执行）。你要评估一下"可能的权限组合总数"是不是大到无法穷举测试。"也就几百种吧？"老板问。你不知道。因为你缺的就是计数的数学工具。
加法原理：做一件事有 m 种互斥的方法，方法一有 n₁ 种方式，方法二有 n₂ 种方式……总方式数为 n₁ + n₂ + ...。
乘法原理：做一件事分 k 步，第 1 步有 n₁ 种方式，第 2 步有 n₂ 种方式……总方式数为 n₁ × n₂ × ...。
五个角色、二十个资源、三种操作：
- 每个资源对每个角色有三种可能的权限状态
- 总组合数 = 3^(5 × 20) = 3^100
这个数字大到不可穷举测试。你现在能回答老板了——也需要说服他做基于策略的测试，而不是穷举。
排列：从 n 个不同元素中取 r 个有序排列。
P(n, r) = n! / (n - r)!
如从 10 个数字中选 4 位密码：P(10, 4) = 10 × 9 × 8 × 7 = 5040。
组合：从 n 个不同元素中取 r 个（不计顺序）。
C(n, r) = n! / (r! × (n - r)!)
从 8 人中选 3 人出差：C(8, 3) = 8! / (3! × 5!) = 56。
关键区别：排列是有序的（密码 1234 ≠ 4321），组合是无序的（出差团队{张三、李四、王五} 和 {王五、李四、张三} 是同一个方案）。
帕斯卡恒等式：C(n, k) = C(n-1, k-1) + C(n-1, k)。这个公式的直观解释：固定一个元素，包含它的组合数 C(n-1, k-1)，不包含它的组合数 C(n-1, k)。它是动态规划求解组合数的数学基础。
鸽巢原理：n+1 个鸽子放入 n 个鸽巢，至少有一个鸽巢里有不少于 2 只鸽子。朴素到近乎废话，但它能导出非平凡结论：
- 在 366 个人中，至少有两个人生日相同（一年最多 365 天）。
- 在 5 个整数中，至少有 3 个奇偶性相同（因为奇数/偶数只有两类，5 放 2 个鸽巢）。
这个原理在哈希碰撞证明中反复出现：如果哈希函数的输出空间小于输入空间，碰撞必然存在。
常见陷阱
- 混淆排列和组合。问"顺序重要吗"是区分的关键。
- 重复计数。在计算"至少一个条件满足"时容易重复计算满足多个条件的方案——这就是包含-排除原理的用武之地。
- 认为 0! = 0。实际 0! = 1——这是一种约定，保证组合公式在 n = r 时成立。
通关挑战
- 一个班级有 30 人，选班长、副班长、学习委员各一人，有多少种选法？
- 10 个不同的书籍放到 3 个书架上（书架有顺序），每个书架至少一本，有多少种放法？
- 用 Python 实现 C(n, k) 的两种方法：阶乘公式和动态规划（帕斯卡三角）。
旅人笔记
排列是"有序的选择"，组合是"无序的选子集"。加法原理和乘法原理是计数的两个基本工具，鸽巢原理告诉你"一定存在"——它们共同构成了你分析系统状态空间的第一套武器。
→ 下一站预告：集合和组合都在讨论"哪些元素"，但元素之间的关系可以用图来描述——图论把你从静态集合带到动态关系。