第 56 章 有多少种可能——排列组合基础
🏗️ 前情回顾：第 55 章你学会了辗转相除法——一个两千年前的算法，至今仍是最快求 GCD 的方式。求 GCD 时你第一次感受到"数学优雅"的力量：一个简单的关系（gcd(a,b)=gcd(b,a%b)）就能四两拨千斤。这一章我们继续挖掘数学在竞赛中的威力——但换一个完全不同的角度：计算"有多少种可能"。这道题是竞赛的常客，也是组合数学的第一课。
🎯 本章目标
学完这一章，你能：
- 区分加法原理和乘法原理，在合适场景应用
- 计算排列数 A(n, m) 和组合数 C(n, m)
- 理解杨辉三角与组合数递推公式的关系
- 用递推（动态规划思想）计算组合数
- 了解组合数取模的基本处理
- 用鸽巢原理（抽屉原理）解决简单问题
📖 故事引入
选修课的烦恼
新学期开始，高中部开设了 5 门选修课：编程、摄影、书法、辩论、天文。学校规定：每个学生必须选 恰好 2 门。
小明在教务处门口掰手指："5 门里面选 2 门，有多少种选法？"
他先列了一下：编程+摄影、编程+书法、编程+辩论、编程+天文、摄影+书法、摄影+辩论、摄影+天文、书法+辩论、书法+天文、辩论+天文……一共 10 种。
小红说："别傻了，我知道公式——C(5,2) = 5×4/2 = 10。"
小明惊讶："你咋算的？"
小红笑道："第一门有 5 种选择，第二门有 4 种选择，所以 5×4=20。但（编程+书法）和（书法+编程）是同一种选法——每种被算了 2 遍，所以除以 2。"
这就是组合数的直觉：先排列再除去重复。
密码锁的故事
另一个场景：一个 3 位数字密码锁，每位可以是 0~9。有多少种可能的密码？
这个简单：第一位 10 种，第二位 10 种，第三位 10 种 → 10×10×10 = 1000 种。
这背后是乘法原理——每一步的选择数相乘。
🧱 知识讲解
56.1 加法原理与乘法原理
这是组合计数最底层的两块基石。
加法原理：做一件事有几种互斥的方法，每种方法有各自的方案数，总方案数 = 各方法方案数之和。
例如：从北京到上海，可以坐飞机（3 个航班）或坐高铁（5 个车次），选一种交通方式 → 3 + 5 = 8 种选择。
乘法原理：做一件事分若干步骤，每步有各自的方案数，总方案数 = 各步方案数之积。
例如：午餐选 1 份主食（米饭/面条，2 种）和 1 份菜（宫保鸡丁/红烧肉/素三鲜，3 种）→ 2 × 3 = 6 种搭配。
分辨口诀：分类用加法，分步用乘法。"或者"→ 加法，"并且"→ 乘法。
56.2 排列数 A(n, m)
从 n 个不同元素中取 m 个，按顺序排成一列，有多少种排法？
- 第 1 个位置：n 种选择
- 第 2 个位置：n-1 种选择
- 第 3 个位置：n-2 种选择
- …
- 第 m 个位置：n-m+1 种选择
乘起来：
A(n, m) = n × (n-1) × (n-2) × … × (n-m+1) = n! / (n-m)!
例如：从 5 个学生中选 3 个排成一排照相 → A(5, 3) = 5×4×3 = 60 种排法。
特别地，当 m = n 时，A(n, n) = n!（n 的阶乘），即 n 个元素的全排列。
// 计算 A(n, m) —— 注意可能溢出
long long A(int n, int m) {
long long result = 1;
for (int i = 0; i < m; i++) {
result *= (n - i); // 依次乘 n, n-1, n-2, ...
}
return result;
}
// A(5, 3) = 5×4×3 = 6056.3 组合数 C(n, m)
从 n 个不同元素中取 m 个，不考虑顺序，有多少种取法？
排列数 A(n, m) 先考虑了顺序。但选出的 m 个元素有 m! 种排列方式，每种对应"同一种选法"。因此：
C(n, m) = A(n, m) / m! = n! / (m! × (n-m)!)
回到开头：C(5, 2) = 5! / (2! × 3!) = 120 / (2 × 6) = 10 ✓。
// 直接公式法：C(n, m) = n×(n-1)×...×(n-m+1) / m!
long long C(int n, int m) {
if (m > n - m) m = n - m; // 用对称性：C(n,m) = C(n, n-m)
long long result = 1;
for (int i = 1; i <= m; i++) {
result = result * (n - i + 1) / i; // 先乘后除，保证整除
}
return result;
}
// C(5, 2) = 5/1 × 4/2 = 5×2 = 10💡
if (m > n-m) m = n-m;是个小优化：C(100, 98) 不应该算 100×99×…/98!，而是利用 C(100,98) = C(100,2) 只算两个因子。
56.4 杨辉三角与组合数递推
把组合数排成三角形，你发现了什么？
C(0,0)
C(1,0) C(1,1)
C(2,0) C(2,1) C(2,2)
C(3,0) C(3,1) C(3,2) C(3,3)代入数值：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1这就是杨辉三角。它的核心规律是：每个数等于它"肩上"两个数之和：
C(n, m) = C(n-1, m-1) + C(n-1, m)
为什么？从 n 个元素中选 m 个，可以分两种情况：
- 选了第 n 个元素：剩下 n-1 个中选 m-1 个 → C(n-1, m-1)
- 没选第 n 个元素：剩下 n-1 个中选 m 个 → C(n-1, m)
- 加法原理：两情况互斥 → 总数为两数之和
这个递推公式非常强大：避免了大数阶乘，且天然适配动态规划。
const int MAXN = 100;
long long comb[MAXN][MAXN]; // comb[n][m] = C(n, m)
void buildPascal(int n) {
for (int i = 0; i <= n; i++) {
comb[i][0] = comb[i][i] = 1; // C(n,0) = C(n,n) = 1
for (int j = 1; j < i; j++) {
comb[i][j] = comb[i-1][j-1] + comb[i-1][j];
}
}
}
// 之后直接查表：comb[5][2] = 10递推法的优势：O(n²) 建好表后，查询是 O(1)。而且配合取模非常方便。
56.5 组合数取模（入门）
竞赛中组合数经常要对一个大质数取模（如 10⁹+7），因为实际值可能大得离谱。用杨辉三角递推取模最简洁：
const int MOD = 1000000007;
long long comb[MAXN][MAXN];
void buildPascalMod(int n) {
for (int i = 0; i <= n; i++) {
comb[i][0] = comb[i][i] = 1;
for (int j = 1; j < i; j++) {
comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
}
}
}当 n 较大（如 10⁶）时，杨辉三角的 O(n²) 空间不够。这时需要用阶乘 + 逆元的方式——属于进阶内容，下一册专题讲解。
56.6 鸽巢原理（抽屉原理）
这是组合数学中最简单也最强大的定理之一：
把 n+1 个苹果放进 n 个抽屉，至少有一个抽屉里至少有 2 个苹果。
推而广之：把 kn+1 个苹果放进 n 个抽屉，至少有一个抽屉里至少有 k+1 个苹果。
看似简单，却能推出很多不那么显然的结论：
- 13 个人中至少有两个人的生日在同一个月份（12 个月，13 个人）
- 从 1 到 2n 中任取 n+1 个数，必有两个数互质（它们相差 1）
- 一个地区 50 万人，头发数量不超过 20 万根 → 至少 3 个人的头发数相同
// 鸽巢原理的一个简单应用
// 给定 n+1 个 1~n 之间的整数，证明必有重复 → 实际上直接输出即可
// 输入 n+1 个数，找出任意一对相同的
#include <vector>
int findDuplicate(vector<int>& nums) {
vector<bool> seen(nums.size(), false);
for (int x : nums) {
if (seen[x]) return x; // 鸽巢原理保证一定存在重复
seen[x] = true;
}
return -1; // 实际上不会执行到这里
}✋ 动手试试
试试 1：写程序分别计算 A(5,2)、A(5,3)、A(6,3)。验证：A(5,2)=20, A(5,3)=60, A(6,3)=120。
试试 2：用公式法计算 C(10,3) 和 C(10,7)，验证它们相等（C(n,m)=C(n,n-m) 对称性）。
试试 3：用杨辉三角递推生成前 10 行（n=0 到 9），输出三角形。看看第 5 行（n=5）是不是"1 5 10 10 5 1"。
试试 4（探索）：枚举验证"从 1~10 中任取 6 个数，必有两个数互质"。写程序对所有 C(10,6)=210 种取法逐一验证。
⚠️ 容易犯的错
错 1：混淆排列和组合
❌ 选课问题用 A(5,2) = 20
✅ "选课"不考虑顺序 → 用 C(5,2) = 10。先想清楚要不要顺序！
错 2：阶乘溢出
❌ int factorial(int n) { int f=1; for(int i=2;i<=n;i++) f*=i; return f; }
→ 13! 就已经超过 int 范围了！
✅ 用 long long，或改用递推公式避免大阶乘。
错 3：杨辉三角数组下标越界
❌ comb[i-1][j] 当 j=0 时访问 comb[i-1][-1]
✅ 初始化边界 comb[i][0] = comb[i][i] = 1，内层循环从 j=1 到 j=i-1。
错 4：把鸽巢原理的"至少"理解成"恰好"
❌ "把 5 个苹果放 3 个抽屉，有一个抽屉恰好有 3 个苹果"
✅ 鸽巢原理说的是"至少"——至少有一个抽屉有 ≥ ceil(5/3) = 2 个苹果。
📝 练习
基础题
1. 填空题
（1）完成一件工作，可以用方法 A（3 种方案）或方法 B（5 种方案），总共有 ____ 种方案。这运用的是 ____ 原理。
（2）A(6, 2) = ____，C(6, 2) = ____。
（3）杨辉三角递推公式：C(n, m) = ____ + ____。
（4）C(10, 8) = C(10, ____)（利用对称性）。
（5）把 8 个苹果放进 7 个抽屉，至少有一个抽屉有 ____ 个苹果。
2. 读代码写结果
long long c[10][10];
for (int i = 0; i <= 6; i++) {
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j++)
c[i][j] = c[i-1][j-1] + c[i-1][j];
}
cout << c[6][3] << endl;输出是多少？
提高题
3. 编程题 — 路线的数量
一个 n×m 的网格，从左上角出发，每次只能向右或向下走一步，走到右下角有多少种走法？
输入：2 3（2行3列）
输出：10
（解释：总共需要走 (n+m) 步，其中选 m 步向右走 → C(n+m, m)）4. 编程题 — 鸽巢原理：生日问题
输入一个班级的人数 N，用鸽巢原理分析：至少有多少人的生日在同一个月份？
（提示：用 ceil(N / 12.0) 即可，但不用浮点——用 (N + 11) / 12 整数上取整。）
挑战题
5. 编程题 — 组合数取模
输入 n 和 m（0 ≤ m ≤ n ≤ 1000），输出 C(n, m) mod 1000000007 的值。要求用杨辉三角递推法实现。
输入：10 5
输出：252
输入：100 50
输出：538992043 （C(100,50) 本身是个 29 位数，取模后才这么大）6. 编程题 — 排列的字典序
输入 n（1 ≤ n ≤ 8），按字典序（从小到大）输出 1~n 的所有全排列。
输入：3
输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1（提示：可以用递归 + bool used[] 标记，也可以用 STL 的 next_permutation。递归版本等于 DFS 搜索，是回溯算法的经典入门题。）
🧠 本章小结
加法原理：分类 → 相加 "或者"
乘法原理：分步 → 相乘 "并且"
排列 A(n,m) = n!/(n-m)! 考虑顺序
组合 C(n,m) = n!/(m!(n-m)!) 不考虑顺序
对称性：C(n,m) = C(n, n-m)
杨辉三角递推：
C(n,m) = C(n-1,m-1) + C(n-1,m)
建表 O(n²)，查询 O(1)，天然支持取模
鸽巢原理：n+1个鸽子进n个巢 → 至少有一个巢≥2只
推广：kn+1个鸽子进n个巢 → 至少有一个巢≥k+1只📝 配套练习
共7题。加法/乘法原理→排列→组合→杨辉三角→鸽巢→取模，组合数学入门全覆盖。。★核心（课堂必做） ◆拓展（课后练习）
💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 18 道◆拓展题，覆盖不同变式和细节。
配套练习
共7题。加法/乘法原理→排列→组合→杨辉三角→鸽巢→取模，组合数学入门全覆盖。★核心（课堂必做） · ◆拓展（课后练习）
练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 18 道◆拓展题，覆盖不同变式和细节。
自查清单：
- [ ] 我能区分加法原理和乘法原理的使用场景
- [ ] 我能写出 A(n,m) 和 C(n,m) 的计算公式
- [ ] 我理解为什么 C(n,m) = C(n, n-m)
- [ ] 我能用杨辉三角递推计算组合数
- [ ] 我能写出带取模的杨辉三角代码
- [ ] 我理解鸽巢原理并能用它解释简单现象
- [ ] 我知道大阶乘要用 long long 或取模
🚀 下章预告
恭喜你！到这里，你已经学完了《C++ 编程之路》上册的全部内容。从第一个 Hello, World! 到链表、栈、队列，再到数论和排列组合——你具备了扎实的 C++ 编程基础和算法入门知识。
下册将带你进入更广阔的算法世界：深度优先搜索（DFS）与广度优先搜索（BFS）、动态规划（DP）、图论基础、更高级的数据结构（树、堆、并查集）……这些工具将让你真正有能力参加信息学竞赛。
在上册的最后，建议你回头翻一翻各章的"自查清单"，看看哪些地方还需要巩固。记住：编程是练出来的，不是看出来的。 多动手、多敲代码、多调试——每解决一个 bug，你就强了一分。
我们下册见！🚀