第3章排列与组合

🎯 本章学习目标

通过本章的学习，你将能够：

理解排列概念：掌握排列的定义，知道排列是有序的
理解组合概念：掌握组合的定义，知道组合是无序的
辨析排列组合：能准确判断一个问题是排列还是组合
掌握排列数公式：熟练计算 A(n,m)
掌握组合数公式：熟练计算 C(n,m)
理解组合数性质：掌握 C(n,m)=C(n,n-m) 等重要性质
掌握捆绑法：解决相邻元素的排列问题
掌握插空法：解决不相邻元素的排列问题
理解阶乘溢出：知道阶乘增长很快，会处理大数取模
应对真题题型：能解决选择、判断、计算等各类排列组合题目

🗺️ 本章知识图谱

排列与组合
├── 排列（有序）
│   ├── 定义：从n个中选m个，排成一排
│   ├── 排列数 A(n,m) = n!/(n-m)!
│   ├── = n × (n-1) × ... × (n-m+1)
│   ├── 全排列 A(n,n) = n!
│   └── 典型场景
│       ├── 排队/拍照
│       ├── 分工/任职
│       └── 密码/数字排列
├── 组合（无序）
│   ├── 定义：从n个中选m个，不排顺序
│   ├── 组合数 C(n,m) = n!/(m!(n-m)!)
│   ├── = A(n,m) / m!
│   ├── 性质
│   │   ├── C(n,m) = C(n,n-m)
│   │   ├── C(n,0) = C(n,n) = 1
│   │   └── C(n,m) = C(n-1,m-1) + C(n-1,m)
│   └── 典型场景
│       ├── 选课/选人参会
│       ├── 分组/握手
│       └── 子集/选队
├── 阶乘
│   ├── n! = n × (n-1) × ... × 1
│   ├── 0! = 1
│   ├── 增长极快（12!溢出int，20!溢出long long）
│   └── 取模运算（每次乘后取模）
├── 经典计数技巧
│   ├── 捆绑法（相邻问题）
│   │   ├── 把相邻元素捆成一个整体
│   │   ├── 先排整体，再排内部
│   │   └── 别忘了乘内部排列数
│   ├── 插空法（不相邻问题）
│   │   ├── 先排其他元素
│   │   ├── 再把不相邻的插入空隙
│   │   └── n个元素有n+1个空隙（含两端）
│   └── 补集法（至少/至多）
│       ├── 正难则反
│       └── 总数 - 不满足的
├── 组合数计算方法
│   ├── 公式法（直接计算）
│   ├── 递推法（杨辉三角）
│   └── 预处理阶乘+逆元（模意义下）
└── 易错点
    ├── 有序/无序判断错误
    ├── 重复计数
    ├── 阶乘溢出
    ├── 捆绑漏乘内部排列
    └── 插空数错空隙数

一、排列与组合：一字之差，天壤之别

1.1 从两个小问题说起

问题 A：从甲、乙、丙 3 名同学中选出 2 名，分别担任班长和副班长，有多少种方案？
问题 B：从甲、乙、丙 3 名同学中选出 2 名参加座谈会，有多少种方案？

问题 A 中，"甲当班长、乙当副班长"与"乙当班长、甲当副班长"是两种不同方案——选出来还要排顺序，这是排列，答案 A(3,2) = 6。

问题 B 中，{甲, 乙} 和 {乙, 甲} 是同一组人——只关心选出了谁，这是组合，答案 C(3,2) = 3。

🔥 高频考点：判断排列还是组合，只问自己一句话——"交换两个元素的位置，结果还算不算同一种？" 算同一种 → 组合（无序）；不算 → 排列（有序）。

1.2 核心公式

概念	公式	含义	典型场景
排列数 A(n,m)	$A(n,m)=\dfrac{n!}{(n-m)!}=n(n-1)\cdots(n-m+1)$	从 n 个元素中有序选 m 个	排队、拍照、分工、密码
全排列	$A(n,n)=n!$	n 个元素全部排成一列	排序、洗牌
组合数 C(n,m)	$C(n,m)=\dfrac{n!}{m!(n-m)!}$	从 n 个元素中无序选 m 个	选课、分组、握手、子集

两者的桥梁公式：

A(n,m) = C(n,m) \times m!

先无序地选出 m 个人（C(n,m)），再给他们排顺序（m!），就得到有序方案数。这个关系是"漏除阶乘"类错误的理论根源，务必记牢。

📎 注：部分教材把排列数记作 P(n,m) 或 $A_n^m$ ，组合数记作 $\binom{n}{m}$ ，含义完全相同，真题中遇到不要慌。

二、阶乘：增长有多快？溢出怎么破？

排列数与组合数都建立在阶乘之上，而阶乘是增长最凶猛的函数之一。

2.1 阶乘增长速查表

n	n!	约等于	C++ `int` 装得下？	C++ `long long` 装得下？
10	3,628,800	3.6×10⁶	✅	✅
12	479,001,600	4.8×10⁸	✅（极限）	✅
13	6,227,020,800	6.2×10⁹	❌ 溢出	✅
20	2,432,902,008,176,640,000	2.4×10¹⁸	❌	✅（极限）
21	51,090,942,171,709,440,000	5.1×10¹⁹	❌	❌ 溢出

⚠️ 易错点：int 撑不过 13!，long long（约 9.2×10¹⁸）撑不过 21!。写阶乘循环时，数据类型要提前想好，别等答案变成负数或乱码才排查。

2.2 大数取模：边乘边模

竞赛题中组合数答案动辄要求对质数 $p=10^9+7$ 取模。利用 $(a \times b) \bmod p = ((a \bmod p)\times(b \bmod p)) \bmod p$ ，每乘一步就取一次模，中间结果永远不溢出：

cpp

// C++11：阶乘取模
#include <iostream>
using namespace std;
const long long MOD = 1000000007;

int main() {
    int n; cin >> n;
    long long fact = 1;
    for (int i = 1; i <= n; i++) {
        fact = fact * i % MOD;   // 边乘边取模
    }
    cout << fact << endl;
    return 0;
}

⚠️ 易错点：C++ 中两个 int 相乘会先按 int 相乘（可能已溢出）再提升，赋值给 long long 也救不回来。保险写法是 (long long)a * b % MOD，或干脆把变量声明为 long long。

三、组合数的三种求法

方法一：公式法（小数据精确计算）

直接用 $C(n,m)=\dfrac{n!}{m!(n-m)!}$ 。为避免中间结果过大，可利用对称性 $C(n,m)=C(n,n-m)$ 并采用"乘一项除一项"的写法（每步结果都是整数）：

cpp

// C++11：公式法求组合数（n ≤ 60 左右，long long 精确值）
long long C_formula(int n, int m) {
    if (m < 0 || m > n) return 0;   // 边界：C(n,0)=1，m>n 时为 0
    if (m > n - m) m = n - m;       // 对称性，减少循环次数
    long long res = 1;
    for (int i = 1; i <= m; i++) {
        res = res * (n - m + i) / i;  // 每步都能整除
    }
    return res;
}

方法二：递推法（与第4章杨辉三角呼应 🎬）

组合数有一个优美的递推关系：

C(n,m) = C(n-1,m-1) + C(n-1,m)

组合意义：从 n 个人里选 m 个，要么选"第 n 个人"（再从前面 n−1 人中选 m−1 人），要么不选他（从前面 n−1 人中选 m 人），两类相加。边界 $C(n,0)=C(n,n)=1$ 。

cpp

// C++11：递推法预处理组合数表（取模）
const int MAXN = 1005;
long long C[MAXN][MAXN];
void init(int n) {
    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]) % MOD;
    }
}
// 查询：cout << C[10][3];  → 120

💡 埋个伏笔：这张递推表就是大名鼎鼎的杨辉三角！第 4 期我们会专门展开它的性质、打印与各种考法。

方法三：逆元法（入门，模数为质数时）

取模意义下不能直接做除法。当模数 p 是质数（如 10⁹+7）时，由费马小定理，a 的逆元为 $a^{-1} \equiv a^{p-2} \pmod p$ ，于是：

C(n,m) \equiv n! \times (m!)^{-1} \times ((n-m)!)^{-1} \pmod p

预处理阶乘与逆阶乘后，O(1) 查询，可支持 n 到 10⁶ 量级：

cpp

// C++11：逆元法（快速幂 + 阶乘预处理）
const int MAXN = 1000005;
long long fact[MAXN], invfact[MAXN];

long long qpow(long long a, long long b) {   // 快速幂 a^b mod MOD
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
void init(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
    invfact[n] = qpow(fact[n], MOD - 2);     // 费马小定理求逆元
    for (int i = n; i >= 1; i--) invfact[i-1] = invfact[i] * i % MOD;
}
long long C_inv(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fact[n] * invfact[m] % MOD * invfact[n-m] % MOD;
}

三种方法对比总表

方法	核心思路	预处理	单次查询	适用场景
公式法	阶乘相除/逐项乘除	无	O(m)	n 很小（≤60）、无需取模、查询少
递推法	杨辉三角递推	O(n²)	O(1)	n ≤ 几千、多次查询、取模均可
逆元法	阶乘 × 费马小定理	O(n)	O(1)	n 很大（10⁶级）、模数为质数

四、经典计数技巧：捆绑法 & 插空法

4.1 捆绑法——"必须相邻"

遇到"某几个元素必须排在一起"：把它们捆成一个"大元素"参与整体排列，最后乘以内部排列数。

例：5 人排队，甲、乙必须相邻。把甲乙捆成 1 个整体，相当于 4 个元素全排列：4!；甲乙内部可互换：2!。答案： $2! \times 4! = 48$ 。

4.2 插空法——"不能相邻"

遇到"某几个元素不能相邻"：先排没有限制的元素，再把受限元素插入它们的空隙中。

例：5 人排队，甲、乙不能相邻。先排其余 3 人：3!；3 个人排好后形成 4 个空隙（含两端！），从中选 2 个放入甲乙（有序）：A(4,2)=12。答案： $3! \times A(4,2) = 6 \times 12 = 72$ 。验证（补集思想）： $5! - 48 = 120 - 48 = 72$ ✓。

⚠️ 易错点：插空时空隙数是 n+1（n 个元素排好，两端也算），不是 n−1！捆绑法最后别忘了乘内部排列。

4.3 附带一提：平均分组要"除阶乘"

6 人平均分成 3 组（组无编号），方案数为：

\frac{C(6,2)\cdot C(4,2)\cdot C(2,2)}{3!} = \frac{15\times6\times1}{6} = 15

分步选取时，3 个组的先后顺序被重复计数了 3! 次，必须除掉；若 3 个组要去 3 个不同的班级（组有编号），则不除，答案为 90。

五、递进例题精析

例题 1（排队问题 · 排列 + 捆绑/插空）

5 名同学排成一排照相：

共有多少种排法？
甲、乙必须相邻，有多少种？
甲、乙不能相邻，有多少种？

解析：

全排列： $5! = 120$
捆绑法： $2! \times 4! = 48$
插空法： $3! \times A(4,2) = 72$ （或补集法 $120-48=72$ ）

cpp

// C++11
#include <iostream>
using namespace std;
long long fact(int n) {
    long long r = 1;
    for (int i = 2; i <= n; i++) r *= i;
    return r;
}
int main() {
    cout << fact(5) << endl;            // (1) 120
    cout << 2 * fact(4) << endl;        // (2) 捆绑：2!*4! = 48
    cout << fact(3) * (4 * 3) << endl;  // (3) 插空：3!*A(4,2) = 72
    return 0;
}

例题 2（选课问题 · 组合 + 补集法）

学校开设 10 门选修课，每名同学需选 4 门：

一共有多少种选法？
若甲、乙两门课至少选一门，有多少种选法？

解析：

无序选取： $C(10,4) = 210$
"至少选一门"正面分类（选甲不选乙、选乙不选甲、都选）容易算重，补集法更清爽：总数 − 两门都不选（从其余 8 门选 4 门）： $C(10,4) - C(8,4) = 210 - 70 = 140$

cpp

// C++11
#include <iostream>
using namespace std;
long long C(int n, int m) {
    if (m < 0 || m > n) return 0;
    if (m > n - m) m = n - m;
    long long r = 1;
    for (int i = 1; i <= m; i++) r = r * (n - m + i) / i;
    return r;
}
int main() {
    cout << C(10, 4) << endl;              // 210
    cout << C(10, 4) - C(8, 4) << endl;    // 140（补集法）
    return 0;
}

🔥 高频考点："至少/至多"类问题，优先考虑补集法（总数减去对立事件），比正面分类更不容易重复计数。

例题 3（网格路径数 · 组合的几何模型）

如图，在 m×n 的方格网格中，从左上角 A 走到右下角 B，每步只能向右或向下，问共有多少条不同路径？（示例：3×3 网格）

解析：无论怎么走，总共要走 m+n 步，其中 m 步向右、n 步向下。路径的区别仅在于"哪 m 步向右"——这正是从 m+n 步中无序选 m 步：

\text{路径数} = C(m+n,\ m)

3×3 网格： $C(6,3) = 20$ 。数据大时用逆元法取模：

cpp

// C++11：路径数对 1e9+7 取模（逆元法）
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
long long qpow(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
long long fact(int x) {
    long long r = 1;
    for (int i = 2; i <= x; i++) r = r * i % MOD;
    return r;
}
int main() {
    int m, n; cin >> m >> n;
    long long ans = fact(m + n);
    ans = ans * qpow(fact(m), MOD - 2) % MOD;
    ans = ans * qpow(fact(n), MOD - 2) % MOD;
    cout << ans << endl;      // 输入 3 3 → 20
    return 0;
}

例题 4（错排问题入门 · 递推计数）

n 封信装入 n 个写好地址的信封，要求每封信都装错信封，求方案数 D(n)。

**解析：**考虑第 1 封信，它有 n−1 种错误放法。假设它被放进了第 k 个信封：

若第 k 封信恰好放进第 1 个信封：两封信互换，剩下 n−2 封错排，D(n−2) 种；
若第 k 封信不放进第 1 个信封：等价于剩下 n−1 封信的错排问题，D(n−1) 种。

于是得到错排递推式：

D(n) = (n-1)\times(D(n-1) + D(n-2)),\quad D(1)=0,\ D(2)=1

前几项：D(3)=2，D(4)=9，D(5)=44。

cpp

// C++11：错排数（取模）
#include <iostream>
using namespace std;
const long long MOD = 1000000007;
int main() {
    int n; cin >> n;
    if (n == 1) { cout << 0 << endl; return 0; }
    long long d1 = 0, d2 = 1;          // D(1)=0, D(2)=1
    for (int i = 3; i <= n; i++) {
        long long cur = (i - 1) * (d1 + d2) % MOD;
        d1 = d2; d2 = cur;
    }
    cout << d2 << endl;                // n=4 → 9
    return 0;
}

💡 错排是八级组合题的"常客"，递推式的推导思想（分类讨论 + 子问题化）也是动态规划的雏形，值得反复体会。

六、常见变式小补充

考场上排列组合还会有几个"换皮"出现，掌握套路后都是送分：

变式	模型	结论	说明
圆排列	n 个人围圆桌就座	$(n-1)!$	旋转后相同视为同一种，固定 1 人位置再排其余 n−1 人
定序排列	n 人排队，其中 k 人相对顺序固定	$\dfrac{n!}{k!}$	这 k 人的 k! 种排法里只算 1 种，故除掉
多排问题	n 人分前后排就座	本质仍是 n!	把前后排"拉直"成一列即可
可重复组合	从 n 种球中取 m 个（可放回，无序）	$C(n+m-1, m)$	隔板法：转化为 m 个相同球放入 n 个盒子

🔥 高频考点：圆排列为什么是 (n−1)! 而不是 n!? 因为圆桌没有"首尾位置"之分，整体旋转得到的是同一种坐法。如果桌子上有固定编号座位（或项链有扣），就退化为普通排列 n!。

隔板法示例：把 10 个相同的苹果分给 3 个小朋友，每人至少 1 个，有几种分法？ 10 个苹果排成一行，中间有 9 个空隙，插入 2 块"隔板"即分成 3 份： $C(9,2) = 36$ 种。

七、易错点大盘点 🚨

#	易错点	正确做法
1	⚠️ 有序/无序判断错	排队、拍照、分工、密码 → 排列；选课、分组、握手、子集 → 组合
2	⚠️ 重复计数	"至少选一个"等问题优先用补集法；分类时保证各类互不重叠
3	⚠️ 漏除阶乘	平均分组除以组数阶乘；定序问题除以定序元素阶乘
4	⚠️ 阶乘溢出	int ≤ 12!，long long ≤ 20!；取模在每次乘法后进行
5	⚠️ C++ 乘法溢出	两个 int 相乘前先 `(long long)` 强转，或变量直接用 long long
6	⚠️ 组合数边界	$C(n,0)=1$ ； $m>n$ 时 $C(n,m)=0$ ，别让数组越界
7	🔥 捆绑/插空漏项	捆绑乘内部排列；插空数空隙为 n+1（含两端）

🔥 考场口诀：先判有序无序，再选排列组合；相邻捆绑不邻插空，至少至多想补集；阶乘防溢出，分组防漏除。

练习题 4（判断题）

题目： C(10, 3) 和 C(10, 7) 的关系是？（）

A. C(10,3) > C(10,7)
B. C(10,3) < C(10,7)
C. C(10,3) = C(10,7)
D. 无法判断

🔑 点击查看答案与解析

答案： C

解析： 组合数的重要性质：C(n, m) = C(n, n-m)

所以 C(10, 3) = C(10, 10-3) = C(10, 7)

验证：

C(10,3) = 10×9×8 / 3×2×1 = 720/6 = 120
C(10,7) = 10×9×8×7×6×5×4 / 7×6×5×4×3×2×1 = 604800/5040 = 120

相等！

选 C。

💡 为什么相等？因为"选 3 个留下"和"选 7 个去掉"是同一个意思！选 m 个 = 不选 n-m 个。

---

练习题 5（单选题）

题目： 3 个男生和 2 个女生排成一排照相，要求 2 个女生必须相邻，共有多少种排法？（）

A. 24
B. 48
C. 120
D. 96

🔑 点击查看答案与解析

答案： B

解析： 相邻问题用捆绑法：

把 2 个女生捆成一个整体
- 女生内部排列：A(2,2) = 2! = 2 种
现在相当于有 4 个元素（3 个男生 + 1 个"女生捆"）
- 4 个元素全排列：A(4,4) = 4! = 24 种
总排法 = 24 × 2 = 48 种

选 B。

⚠️ 易错点：别忘了乘"捆绑内部"的排列数！只捆不排会漏掉一半答案。

---

练习题 6（单选题）

题目： 3 个男生和 2 个女生排成一排，要求 2 个女生不能相邻，共有多少种排法？（）

A. 36
B. 72
C. 120
D. 24

🔑 点击查看答案与解析

答案： B

解析： 不相邻问题用插空法：

先排男生：3 个男生全排列 → A(3,3) = 3! = 6 种
找空隙：3 个男生形成 4 个空隙（含两端）：_ 男 _ 男 _ 男 _
选空隙放女生：从 4 个空隙中选 2 个放女生 → A(4,2) = 4 × 3 = 12 种
总排法 = 6 × 12 = 72 种

选 B。

💡 记忆口诀：不相邻 → 先排别人 → 再插空。n 个元素有 n+1 个空隙（两端也算）。

---

练习题 7（判断题）

题目： 组合数满足递推关系：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)

两种情况加起来就是总数：C(n, m) = C(n-1, m-1) + C(n-1, m)

💡 这就是杨辉三角的原理！每个数 = 它左上方的数 + 正上方的数。

---

练习题 8（判断题）

题目： 0 的阶乘等于 0。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析：0! = 1，不是 0！

为什么？

数学上规定 0! = 1，这样很多公式才能自洽
比如 C(n,0) = n!/(0! × n!) = 1，这符合"从n个中选0个只有1种选法（什么都不选）"
再比如 A(n,n) = n!，而 A(n,n) 也等于 n!/(n-n)! = n!/0!，所以 0! 必须等于 1

🔥 高频考点：0! = 1 是判断题的常客，千万别记成 0！

---

八、📝 实战练习

练习题 1（单选题）

题目： 从 8 名学生中选出 3 名分别参加语文、数学、英语三科竞赛（每人限报一科），不同的选派方案共有（）种。

A. 56　　B. 336　　C. 24　　D. 512

🔑 点击查看答案与解析

答案： B

**解析：**三科竞赛各不相同，人选确定后还要分配到具体科目，有序选取，用排列数：

A(8,3) = 8\times7\times6 = 336

也可分步用乘法原理：语文科 8 种选法，数学科 7 种，英语科 6 种，8×7×6 = 336。选项 A 是 C(8,3)=56，是"只选出 3 人不分科目"的组合数，掉进无序陷阱。

练习题 2（单选题）

题目： 5 个人站成一排，其中甲、乙两人不能相邻的站法数为（）。

A. 24　　B. 48　　C. 72　　D. 96

🔑 点击查看答案与解析

答案： C

**解析：**插空法——先排其余 3 人：3!=6；3 人排好后形成 4 个空隙（含两端），从中选 2 个放甲、乙（有序）：A(4,2)=12。6×12=72。也可用补集法：5! − 2!×4! = 120 − 48 = 72。两种方法互相验证，答案可靠。

练习题 3（判断题）

题目： long long 类型可以精确存储 25! 的值。

🔑 点击查看答案与解析

答案： 错误 ❌

解析：long long 的上限约为 9.2×10¹⁸，而 20! ≈ 2.43×10¹⁸ 尚能存储，21! ≈ 5.1×10¹⁹ 已经溢出，更不必说 25!（≈ 1.55×10²⁵）。遇到大数阶乘必须改用取模运算或高精度。

九、📊 考点总结表

考点	重要程度	出题形式	易错点
排列vs组合辨析	⭐⭐⭐⭐⭐	选择/判断	有序=排列，无序=组合
排列数 A(n,m)	⭐⭐⭐⭐⭐	选择/计算	n!/(n-m)! = n×(n-1)×...×(n-m+1)
组合数 C(n,m)	⭐⭐⭐⭐⭐	选择/计算/编程	n!/(m!(n-m)!)
组合数性质 C(n,m)=C(n,n-m)	⭐⭐⭐⭐⭐	选择/判断	选m个=不选n-m个
组合数递推公式	⭐⭐⭐⭐⭐	选择/编程	C(n,m)=C(n-1,m-1)+C(n-1,m)
捆绑法（相邻问题）	⭐⭐⭐⭐	选择/计算	别忘了乘内部排列
插空法（不相邻问题）	⭐⭐⭐⭐	选择/计算	n个元素有n+1个空隙
补集法（至少/至多）	⭐⭐⭐⭐	选择/计算	正难则反
0! = 1	⭐⭐⭐⭐	判断/选择	不是0！
阶乘溢出	⭐⭐⭐⭐	选择/编程	int≤12!，long long≤20!
全排列 n!	⭐⭐⭐⭐⭐	选择/计算	n个元素全排列

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│       排列与组合 · 必背速记卡               │
├─────────────────────────────────────────────┤
│  1. 排列有序，组合无序                       │
│  2. 排队/拍照/分工 = 排列                    │
│  3. 选课/分组/握手 = 组合                    │
│  4. A(n,m) = n!/(n-m)! = n×(n-1)×...×(n-m+1)│
│  5. C(n,m) = n!/(m!(n-m)!)                  │
│  6. C(n,m) = C(n,n-m)                       │
│  7. C(n,0) = C(n,n) = 1                     │
│  8. C(n,m) = C(n-1,m-1) + C(n-1,m)         │
│  9. 0! = 1（不是0！）                       │
│ 10. 相邻问题 → 捆绑法（先捆后排）           │
│ 11. 不相邻问题 → 插空法（先排后插）         │
│ 12. n个元素有n+1个空隙（含两端）             │
│ 13. 至少/至多 → 补集法（正难则反）          │
│ 14. 阶乘增长快：int≤12!, long long≤20!     │
│ 15. 全排列 = n!                             │
└─────────────────────────────────────────────┘

第3章 排列与组合 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、排列与组合：一字之差，天壤之别 ​

1.1 从两个小问题说起 ​

1.2 核心公式 ​

二、阶乘：增长有多快？溢出怎么破？ ​

2.1 阶乘增长速查表 ​

2.2 大数取模：边乘边模 ​

三、组合数的三种求法 ​

方法一：公式法（小数据精确计算） ​

方法二：递推法（与第4章杨辉三角呼应 🎬） ​

方法三：逆元法（入门，模数为质数时） ​

三种方法对比总表 ​

四、经典计数技巧：捆绑法 & 插空法 ​

4.1 捆绑法——"必须相邻" ​

4.2 插空法——"不能相邻" ​

4.3 附带一提：平均分组要"除阶乘" ​

五、递进例题精析 ​

例题 1（排队问题 · 排列 + 捆绑/插空） ​

例题 2（选课问题 · 组合 + 补集法） ​

例题 3（网格路径数 · 组合的几何模型） ​

例题 4（错排问题入门 · 递推计数） ​

六、常见变式小补充 ​

七、易错点大盘点 🚨 ​

练习题 4（判断题） ​

练习题 5（单选题） ​

练习题 6（单选题） ​

练习题 7（判断题） ​

练习题 8（判断题） ​

八、📝 实战练习 ​

练习题 1（单选题） ​

练习题 2（单选题） ​

练习题 3（判断题） ​

九、📊 考点总结表 ​

⭐ 必背速记卡 ​

第3章排列与组合

🎯 本章学习目标

🗺️ 本章知识图谱

一、排列与组合：一字之差，天壤之别

1.1 从两个小问题说起

1.2 核心公式

二、阶乘：增长有多快？溢出怎么破？

2.1 阶乘增长速查表

2.2 大数取模：边乘边模

三、组合数的三种求法

方法一：公式法（小数据精确计算）

方法二：递推法（与第4章杨辉三角呼应 🎬）

方法三：逆元法（入门，模数为质数时）

三种方法对比总表

四、经典计数技巧：捆绑法 & 插空法

4.1 捆绑法——"必须相邻"

4.2 插空法——"不能相邻"

4.3 附带一提：平均分组要"除阶乘"

五、递进例题精析

例题 1（排队问题 · 排列 + 捆绑/插空）

例题 2（选课问题 · 组合 + 补集法）

例题 3（网格路径数 · 组合的几何模型）

例题 4（错排问题入门 · 递推计数）

六、常见变式小补充

七、易错点大盘点 🚨

练习题 4（判断题）

练习题 5（单选题）

练习题 6（单选题）

练习题 7（判断题）

练习题 8（判断题）

八、📝 实战练习

练习题 1（单选题）

练习题 2（单选题）

练习题 3（判断题）

九、📊 考点总结表

⭐ 必背速记卡