(2) 排列与组合

GESP C++ 八级考试大纲知识点梳理系列文章：
计数原理：加法与乘法
排列与组合
杨辉三角与组合数
倍增法
代数与平面几何 {: .prompt-tip}

继上一篇我们探讨了计数原理（加法与乘法原理）之后，GESP 八级考纲的第二个重要考点便是排列与组合。

（2）掌握排列与组合基础知识。包括排列、组合的基本概念，及能实现基础排列和组合编程问题的一般方法。 {: .prompt-info}

排列和组合是计数原理的具体应用，也是解决很多复杂算法问题（如概率计算、容斥原理）的工具。

本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。 {: .prompt-warning}

一、基本概念与公式

在区分排列和组合时，最核心的标准仍然是：顺序是否重要。

1.1 排列 (Permutation) —— 有序

从 $n$ 个不同元素中，任取 $m$ ( $m \le n$ ) 个元素按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列。

关键词：有序、位置、队列
符号： $A_n^m$ 或 $P(n, m)$

计算公式：

A_n^m = n \times (n-1) \times (n-2) \times \dots \times (n-m+1) = \frac{n!}{(n-m)!}

特别地：当 $m=n$ 时，称为全排列，公式为 $A_n^n = n!$ 。规定 $0! = 1$ 。

例子： 3 名同学排队领奖，先上台和后上台的站位不同，属于排列问题。方案数： $3! = 3 \times 2 \times 1 = 6$ 种。

1.2 组合 (Combination) —— 无序

从 $n$ 个不同元素中，任取 $m$ ( $m \le n$ ) 个元素并成一组，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合。

关键词：无序、集合、选取
符号： $C_n^m$ 或 $\binom{n}{m}$

计算公式：

C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!}

理解：组合就是在排列的基础上，消去了顺序带来的差异。选出的 $m$ 个元素，它们自己内部的 $m!$ 种排序在组合看来都是同一种情况，所以要除以 $m!$ 。

例子：从 3 名同学中选 2 名去打扫卫生。选 A 和 B，与选 B 和 A 是一回事（都是这两人干活），属于组合问题。方案数： $C_3^2 = \frac{3 \times 2}{2 \times 1} = 3$ 种。

二、重要性质

做题和编程中，经常用到以下两个组合数性质：

对称性：
$C_n^m = C_n^{n-m}$

理解：选 $m$ 个留下的方案数，等于选 $n-m$ 个淘汰的方案数。例如：从 10 个人里选 9 个人去开会 ( $C_{10}^9$ )，等价于选 1 个人留守 ( $C_{10}^1$ )，都是 10 种。

递推公式 (帕斯卡公式)：

C_n^m = C_{n-1}^{m-1} + C_{n-1}^m

理解（特殊元素法）：我们可以用“选课代表”的例子来理解。假设包含小明在内共有 $n$ 个人，要选出 $m$ 个代表。对于小明这个人，命运只有两种可能：

入选：小明占了一个名额，还需要从剩下的 $n-1$ 人中选出 $m-1$ 人，即 $C_{n-1}^{m-1}$ 。
落选：小明没选上，全部 $m$ 个名额都要从剩下的 $n-1$ 人中产生，即 $C_{n-1}^m$ 。

与杨辉三角的联系：杨辉三角（Pascal’s Triangle）的构造规则是“每个数等于它上方两数之和”。如果我们将杨辉三角的第 $n$ 行、第 $m$ 个数记为 $C_n^m$ ，那么这个位置的数正好等于上一行（ $n-1$ 行）的左上角位置（ $m-1$ ）和同列位置（ $m$ ）（注：视对齐方式而定，本质是肩上两数）之和。即： $C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$ 。

这就解释了为什么杨辉三角里的数字恰好就是组合数：

我们把两张表画出来对比一下就清楚了：

表1：杨辉三角（数字版）

       1
     1   1
   1   2   1
  1   3   3   1

规则：两腰是 1，中间的数 = 左上 + 右上（如 $2 = 1+1$ , $3 = 1+2$ ）。

表2：组合数表（公式版）

       C(0,0)
    C(1,0)  C(1,1)
C(2,0)  C(2,1)  C(2,2)

边界：选 0 个 ( $C_n^0$ ) 只有 1 种方法（都不选），对应左腰的 1。选 $n$ 个 ( $C_n^n$ ) 只有 1 种方法（全选），对应右腰的 1。

中间： $C(2,1)$ (2个里选1个) = $C(1,0)$ (前1个里不选X) + $C(1,1)$ (前1个里选X) = $1 + 1 = 2$ 。

结论：既然最外圈的数字一样（都是1），往中间填数的规则也一样（都是加法），那么这两张表填出来的数字肯定是一模一样的。

三、编程实现

在 C++ 编程中，计算排列组合数主要面临的问题是数值溢出。即使是 $20!$ 也会超过 long long 的范围。

3.1 定义法 (适用于 $n$ 较小)

直接利用阶乘公式计算。为了尽量防止溢出，可以边乘边除（先乘大数，再除小数），但在整数运算中需要确保能整除。

最稳妥的方式通常是先计算分子，再计算分母，最后相除。但在编程竞赛中，更推荐用 double 计算近似值（如果不要求精确整数且数值很大），或者在模意义下使用逆元（高级考点）。

对于基础考点，通常数据范围较小 (如 $n \le 20$ )，可以用 long long。

#include <iostream>
using namespace std;

// 计算阶乘
long long factorial(int n) {
    long long res = 1;
    for (int i = 1; i <= n; i++) {
        res *= i;
    }
    return res;
}

// 计算排列数 A(n, m)
long long permutation(int n, int m) {
    if (m < 0 || m > n) return 0;
    // A(n, m) = n! / (n-m)!
    // 优化：直接计算 n * (n-1) * ... * (n-m+1)
    long long res = 1;
    for (int i = 0; i < m; i++) {
        res *= (n - i);
    }
    return res;
}

// 计算组合数 C(n, m)
long long combination(int n, int m) {
    if (m < 0 || m > n) return 0;
    if (m == 0 || m == n) return 1;
    if (m > n / 2) m = n - m; // 利用对称性 C(n, m) = C(n, n-m)

    // 为了防止中间过程溢出，可以考虑杨辉三角递推，或者小心处理乘除
    // 这里演示定义法：C(n, m) = A(n, m) / m!
    
    // 注意：直接运算 A(n, m) / m! 容易在 A(n, m) 阶段就溢出
    // 更好的朴素写法是：res = res * (n-i+1) / i 
    // 原理推导：
    // C(n, i) = C(n, i-1) * (n - i + 1) / i
    // 举例：
    // i=1: res = C(n, 1) = n / 1
    // i=2: res = C(n, 2) = C(n, 1) * (n-1) / 2
    // ...
    // 为什么一定能整除？
    // 数学性质：任意 i 个连续整数的乘积，一定能被 i! 整除。
    // 这里的 res * (n-i+1) 分子部分本质上就是 A(n, i)，即 n * (n-1) * ... * (n-i+1)，是 i 个连续整数的乘积，所以一定能被 i 整除。
    long long res = 1;
    for (int i = 1; i <= m; i++) {
        res = res * (n - i + 1) / i;
    }
    return res;
}

int main() {
    cout << "A(5, 3) = " << permutation(5, 3) << endl; // 5*4*3 = 60
    cout << "C(5, 3) = " << combination(5, 3) << endl; // 60/6 = 10
    return 0;
}

3.2 递推法 / 杨辉三角 (适用于多次查询或取模)

利用 $C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$ 的递推性质，我们可以通过 $O(N^2)$ 的时间复杂度预处理出一个二维数组 C[N][N]。

定位与作用：

以空间换时间：预处理一次后，后续的每次查询仅需 $O(1)$ 。适合询问次数很多（例如 $10^5$ 次询问）的题目。
避开除法：全过程只涉及加法，避免了除法运算带来的浮点误差或复杂的逆元与模运算。

何时需要取模？

组合数增长极快（例如 $C(100, 50)$ 已经天文数字），编程写题时通常题目会要求输出“对 $10^9+7$ 取模后的结果”。

性质： $(A + B) \% P = ((A \% P) + (B \% P)) \% P$ 。

优势：递推法全是加法，可以每步都取模，保证数据永远不超过 long long 范围，非常安全。而定义法涉及除法，除法取模需要用到“逆元”，稍微麻烦一些。

补充：什么是逆元？

在模运算中，我们不能直接做除法（例如 $(A/B)\%P \ne (A\%P)/(B\%P)$ ）。逆元（Inverse Element）就是为了解决“模意义下的除法”而引入的。简单来说，如果要算 $A \div B \pmod P$ ，等价于算 $A \times (B \text{的逆元}) \pmod P$ 。这属于更高级的数论知识（通常在 GESP 更高等级或信奥中涉及），目前只需知道：想在取模的世界里做除法，必须把除法将其转化为乘法。

#include <iostream>
using namespace std;

const int MAXN = 1005;
const int MOD = 1e9 + 7; // 假设题目要求取模

long long C[MAXN][MAXN];

void init_combinations() {
    // 边界条件：C(i, 0) = 1, C(i, i) = 1
    for (int i = 0; i < MAXN; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }
}

int main() {
    init_combinations();
    
    // 查询 C(10, 2)
    cout << "C(10, 2) = " << C[10][2] << endl; // 45
    return 0;
}

优点：

加法运算，不容易溢出（且容易取模）。
$O(N^2)$ 预处理， $O(1)$ 查询。

四、总结

概念	公式	关键点	适用场景
排列	$A_n^m$	有序	排队、排座位、数字组成
组合	$C_n^m$	无序	选人、选球、集合子集

在 GESP 8 级考试中，除了直接计算排列组合数，更重要的是在实际问题（如格路问题、涂色问题、简单的球盒模型）中，能够正确抽象出是使用加法/乘法原理，还是排列/组合公式。

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年2月4日

(1) 计数原理：加法与乘法 (3) 杨辉三角与组合数