本课时有配套视频讲解，购买后即可观看（永久有效）
排列组合概述
一、课上练习
编程练习
- 组合数计算：L3521
二、知识总结
✨ 分类计数原理与加法原理
分类计数原理（加法原理）：完成一件事有 n 类不同的方案，第 i 类方案有 mi 种方法，则完成这件事共有 m1 + m2 + ... + mn 种方法。
关键在于每一类方案都能独立完成这件事，各类方案之间是互斥的关系。
✨ 分步计数原理与乘法原理
分步计数原理（乘法原理）：完成一件事需要 n 个步骤，第 i 步有 mi 种方法，则完成这件事共有 m1 × m2 × ... × mn 种方法。
关键在于每个步骤都是必需的，只有所有步骤都完成才能完成这件事。
✨ 排列数
排列是指从 n 个不同元素中取出 m 个元素（m <= n），按照一定的顺序排成一列。
排列数公式：
A(n, m) = n! / (n-m)! = n × (n-1) × (n-2) × ... × (n-m+1)
特别地，当 m = n 时，称为全排列：A(n, n) = n!
✨ 组合数
组合是指从 n 个不同元素中取出 m 个元素（m <= n），组成一组，不考虑顺序。
组合数公式：
C(n, m) = A(n, m) / m! = n! / (m! × (n-m)!)
组合数的重要性质：
C(n, m) = C(n, n-m)C(n, 0) = C(n, n) = 1C(n, m) = C(n-1, m-1) + C(n-1, m)（杨辉三角 / 帕斯卡三角）
✨ 执行示例
排列数计算示例：
从 5 个人 {A, B, C, D, E} 中选 3 个人站成一排，有多少种排法？
A(5, 3) = 5! / (5-3)! = 5! / 2! = (5 × 4 × 3 × 2 × 1) / (2 × 1) = 120 / 2 = 60也可以理解为逐步选择：
- 第 1 个位置：5 种选择
- 第 2 个位置：4 种选择（已选 1 人）
- 第 3 个位置：3 种选择（已选 2 人）
- 总计：5 × 4 × 3 = 60
组合数计算示例：
从 5 个人 {A, B, C, D, E} 中选 3 个人组成小组（不考虑顺序），有多少种选法？
C(5, 3) = A(5, 3) / 3! = 60 / 6 = 10验证：所有 10 种组合为 {ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE}
杨辉三角验证 C(5,3)：
1第0行: 1
2第1行: 1 1
3第2行: 1 2 1
4第3行: 1 3 3 1
5第4行: 1 4 6 4 1
6第5行: 1 5 10 10 5 1C(5, 3) = 第 5 行第 3 个数 = 10，与公式计算结果一致。
✨ C++ 代码实现
阶乘与排列数
计算阶乘和排列数
1#include <iostream>
2using namespace std;
3
4// 计算阶乘
5long long factorial(int n) {
6 long long result = 1;
7 for (int i = 2; i <= n; i++) {
8 result *= i;
9 }
10 return result;
11}
12
13// 计算排列数 A(n, m)
14long long A(int n, int m) {
15 long long result = 1;
16 for (int i = n; i > n - m; i--) {
17 result *= i;
18 }
19 return result;
20}
21
22int main() {
23 cout << "A(5,3) = " << A(5, 3) << endl; // 输出 60
24 cout << "5! = " << factorial(5) << endl; // 输出 120
25 return 0;
26}组合数计算
三种方式计算组合数
1#include <iostream>
2using namespace std;
3
4// 方法一：公式法（适合单次计算）
5long long C(int n, int m) {
6 if (m > n - m) m = n - m; // 利用 C(n,m) = C(n,n-m) 优化
7 long long result = 1;
8 for (int i = 0; i < m; i++) {
9 result = result * (n - i) / (i + 1); // 边乘边除，防止溢出
10 }
11 return result;
12}
13
14// 方法二：递推法（杨辉三角，适合批量计算）
15const int MAXN = 35;
16long long c[MAXN][MAXN];
17
18void initCombination() {
19 for (int i = 0; i < MAXN; i++) {
20 c[i][0] = 1;
21 for (int j = 1; j <= i; j++) {
22 c[i][j] = c[i-1][j-1] + c[i-1][j];
23 }
24 }
25}
26
27int main() {
28 // 方法一
29 cout << "C(5,3) = " << C(5, 3) << endl; // 输出 10
30 cout << "C(10,4) = " << C(10, 4) << endl; // 输出 210
31
32 // 方法二
33 initCombination();
34 cout << "c[5][3] = " << c[5][3] << endl; // 输出 10
35 cout << "c[10][4] = " << c[10][4] << endl; // 输出 210
36
37 return 0;
38}杨辉三角打印
打印杨辉三角
1#include <iostream>
2#include <iomanip>
3using namespace std;
4
5int main() {
6 int n;
7 cout << "请输入行数: ";
8 cin >> n;
9
10 long long c[35][35] = {};
11 for (int i = 0; i < n; i++) {
12 c[i][0] = 1;
13 // 打印前导空格
14 for (int k = 0; k < n - i - 1; k++) cout << " ";
15 cout << setw(5) << c[i][0];
16 for (int j = 1; j <= i; j++) {
17 c[i][j] = c[i-1][j-1] + c[i-1][j];
18 cout << setw(6) << c[i][j];
19 }
20 cout << endl;
21 }
22 return 0;
23}输出示例（n=6）：
11
2 1 1
3 1 2 1
4 1 3 3 1
5 1 4 6 4 1
6 1 5 10 10 5 1✨ 取模运算下的组合数
当 n 较大时，组合数可能极大，题目常要求对某个质数 p 取模。
Lucas 定理
当 p 是质数且 n, m 可能很大时，使用 Lucas 定理：
C(n, m) % p = C(n/p, m/p) × C(n%p, m%p) % p
Lucas定理求组合数取模
1#include <iostream>
2using namespace std;
3const int MOD = 1e9 + 7;
4
5long long power(long long a, long long b, long long mod) {
6 long long res = 1;
7 a %= mod;
8 while (b > 0) {
9 if (b & 1) res = res * a % mod;
10 a = a * a % mod;
11 b >>= 1;
12 }
13 return res;
14}
15
16// 费马小定理求逆元：a^(-1) = a^(p-2) (mod p)
17long long inv(long long a, long long mod) {
18 return power(a, mod - 2, mod);
19}
20
21long long C(long long n, long long m, long long mod) {
22 if (m > n) return 0;
23 if (m == 0) return 1;
24 long long num = 1, den = 1;
25 for (long long i = 0; i < m; i++) {
26 num = num * ((n - i) % mod) % mod;
27 den = den * ((i + 1) % mod) % mod;
28 }
29 return num * inv(den, mod) % mod;
30}
31
32long long lucas(long long n, long long m, long long mod) {
33 if (m == 0) return 1;
34 return C(n % mod, m % mod, mod) * lucas(n / mod, m / mod, mod) % mod;
35}
36
37int main() {
38 long long n, m;
39 cin >> n >> m;
40 cout << lucas(n, m, MOD) << endl;
41 return 0;
42}✨ 解题步骤详解
判断用排列还是组合的方法：
- 读题：关键看结果是否与顺序有关
- "排成一排"、"站队"、"第一名第二名" → 排列（顺序有关）
- "选出一组"、"分成小组"、"取出若干" → 组合（顺序无关）
- 判断是加法原理还是乘法原理：
- "分类"（做法 A 或做法 B）→ 加法
- "分步"（先做 A 再做 B）→ 乘法
综合例题： 从 3 名男生和 2 名女生中选出 3 人，要求至少包含 1 名女生，有多少种选法？
方法一（分类）：
- 1 女 2 男：C(2,1) × C(3,2) = 2 × 3 = 6
- 2 女 1 男：C(2,2) × C(3,1) = 1 × 3 = 3
- 总计：6 + 3 = 9
方法二（间接法）：
- 总选法：C(5,3) = 10
- 全是男生：C(3,3) = 1
- 至少 1 女：10 - 1 = 9
✨ 常见错误
- 排列和组合搞混：排列关注顺序（ABC 和 BAC 是不同的），组合不关注顺序（ABC 和 BAC 是同一组）
- 加法和乘法原理用反：分类（互斥的方案）用加法，分步（连续的步骤）用乘法
- 重复计数：在分类讨论时，各类之间必须互斥，不能有交集，否则会重复计数
- 遗漏情况：分类讨论时必须覆盖所有情况，不能有遗漏
- 阶乘计算溢出：n! 增长极快（20! 已超过 long long 范围），大数阶乘需要使用高精度或取模运算
- 组合数计算顺序错误：计算 C(n,m) 时应边乘边除（
result = result * (n-i) / (i+1)），而不是先算完分子再除，否则中间结果可能溢出 - Lucas 定理适用条件：Lucas 定理要求模数 p 是质数，对合数模数无效
✨ 阶乘大小参考表
| n | n! | 说明 |
|---|---|---|
| 0 | 1 | |
| 5 | 120 | |
| 10 | 3,628,800 | int 范围内 |
| 12 | 479,001,600 | int 范围极限 |
| 13 | 6,227,020,800 | 超出 int，需 long long |
| 20 | 2,432,902,008,176,640,000 | long long 范围极限 |
| 21 | 溢出 | 超出 long long，需要高精度或取模 |