📌 组合数学
所属等级：GESP 8级 ｜ 难度： ｜ 关键词：排列组合、容斥原理、递推计数
📝 考纲要求
- 掌握基本计数：加法原理与乘法原理；
- 理解排列数 A(n,m) 与组合数 C(n,m) 的含义与计算；
- 掌握容斥原理：|A∪B| = |A| + |B| − |A∩B|；
- 能用递推/递推式计数（如斐波那契、走楼梯、卡特兰数入门）。
📖 通俗讲解
💡 一句话理解
排列讲究“谁在前谁在后”（顺序有关），组合只看“选了哪些人”（顺序无关）。容斥就是“先全加，再把重复算的减掉”。递推是用小情况推算大情况。
① 组合数 C(n,m) 与杨辉三角
组合数有递推：C(n,m) = C(n-1,m-1) + C(n-1,m)，正是杨辉三角。下面用递推表计算。
🖼️ 图解
杨辉三角：每个数 = 正上方(左上) + 左上方(右上)，即组合数递推
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
↑ ↑
C(4,2)=6 由 3+3 得到：C(n,m)=C(n-1,m-1)+C(n-1,m)C++
#include <iostream>
using namespace std;
const int N = 25;
long long C[N][N]; // C[n][m] 存组合数
// 用杨辉三角递推打表
void init() {
for (int n = 0; n < N; n++) {
C[n][0] = 1; // 选 0 个只有 1 种
C[n][n] = 1; // 全选也只有 1 种
for (int m = 1; m < n; m++) {
// 第 n 行 = 上一行左边 + 上一行自己
C[n][m] = C[n-1][m-1] + C[n-1][m];
}
}
}
int main() {
init();
int n, m; cin >> n >> m;
cout << C[n][m] << endl; // 输出 C(n,m)
return 0;
}输入 / 输出5 2
10
② 递推计数：上楼梯（斐波那契）
问题：一次可走 1 或 2 级台阶，n 级台阶共有多少种走法？
C++
#include <iostream>
using namespace std;
const int N = 55;
long long f[N]; // f[i] 表示 i 级台阶的走法数
int main() {
int n; cin >> n;
f[0] = 1; // 0 级：原地不动算 1 种
f[1] = 1; // 1 级：只有 1 种
for (int i = 2; i <= n; i++) {
// 最后一步要么走1级（来自 i-1），要么走2级（来自 i-2）
f[i] = f[i-1] + f[i-2];
}
cout << f[n] << endl;
return 0;
}输入 / 输出5
8
🔵 核心必背重点
✅ 必背
- 加法原理：分类相加；乘法原理：分步相乘；
- 排列 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)；
- 斐波那契递推：f[i]=f[i-1]+f[i-2]，注意用
long long防溢出。
🔑
记忆口诀：“排列要顺序，组合只看人；容斥先加后减交，递推小推大。”
🔴 考试拉分难点
⚠️ 难点
- 容斥的多集合：三集合容斥为 A+B+C − 两两交 + 三交，符号交替，容易漏；
- 计数与顺序：区分“排列（有序）”还是“组合（无序）”，选错公式整题错；
- 大数溢出：组合数、斐波那契增长极快，n 稍大就要
long long甚至取模； - 递推边界：f[0] 取 0 还是 1 要根据题意定，影响后续所有值。
🟡 高频易错陷阱
🚫 扣分坑点
- 把排列当组合（或反过来），忘记除以顺序数；
- 容斥只加不减，或三集合符号搞反；
- 用
int存组合数导致溢出，应long long； - 递推初值写错（如 f[0]=0 导致 f[2] 也跟着错）；
- 用
bits/stdc++.h（禁用），只用iostream。
🧪 例题演练
例题 1（基础题）：容斥原理计数
题目：1~n 中，能被 a 或 b 整除的数有多少个？（用容斥：被 a 整除 + 被 b 整除 − 被 lcm(a,b) 整除）
C++
#include <iostream>
using namespace std;
// 求最大公约数（辗转相除法）
long long gcd(long long x, long long y) {
while (y) { long long t = x % y; x = y; y = t; }
return x;
}
// 求最小公倍数
long long lcm(long long a, long long b) {
return a / gcd(a, b) * b; // 先除后乘，避免溢出
}
int main() {
long long n, a, b;
cin >> n >> a >> b;
long long cntA = n / a; // 被 a 整除的个数
long long cntB = n / b; // 被 b 整除的个数
long long L = lcm(a, b);
long long cntAB = n / L; // 同时被 a、b 整除（被公倍数整除）
// 容斥：并集 = A + B - 交集
cout << cntA + cntB - cntAB << endl;
return 0;
}输入 / 输出20 2 3
13
例题 2（模拟真题）：网格路径计数（组合应用）
题目：从 (0,0) 走到 (n,m)，每次只能向右或向上走一格，共有多少条路径？（答案 = C(n+m, n)）
C++
#include <iostream>
using namespace std;
const int N = 25;
long long C[N][N];
// 杨辉三角打表求组合数
void init() {
for (int i = 0; i < N; 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];
}
}
int main() {
init();
int n, m; cin >> n >> m;
// 共走 n+m 步，选 n 步向右（其余向上）
cout << C[n + m][n] << endl;
return 0;
}输入 / 输出2 3
10
🚫 错误示范
cout << C[n][m]; —— 把“向右步数 n、向上步数 m”错当成 C(n,m)。实际总步数是 n+m，应在 n+m 中选 n 步向右，应为 C(n+m, n)。
🛡️ 避坑总结
- 排列看顺序、组合不看顺序，先判断是否有序；
- 容斥：并集 = 各集合和 − 两两交 + 三交（符号交替）；
- 组合数用杨辉三角递推，C(n,m)=C(n-1,m-1)+C(n-1,m)；
- 递推计数注意初值与 long long 防溢出；
- 只用 iostream，禁用 bits/stdc++.h。
💡 提示：按 ← → 方向键可在上一 / 下一知识点间快速翻页