排列与组合：有序还是无序，数清楚就靠它们

在日常生活中，我们常常要数一数“有多少种不同的方式”。比如：班级里要从5位同学中选出2位分别当班长和副班长，有多少种选法？如果只是选2位值日生，又有多少种选法？这两种问题的答案不同——前一种要区分谁当班长谁当副班长（顺序重要），后一种不区分先后（顺序不重要）。这就引出了两个重要的计数工具：排列（考虑顺序）和组合（不考虑顺序）。掌握了它们，你就能轻松解决很多“数方案”的题目，比如彩票中奖概率、比赛排名、组队方式等。

生活中的排列与组合

先从一个简单的例子说起：

有三个小朋友：A、B、C。老师要从他们中选两个人去领奖。

如果领奖分金牌和银牌：谁拿金牌、谁拿银牌是有区别的。那么可能的颁奖顺序有： AB（A金牌、B银牌）、BA（B金牌、A银牌）、AC、CA、BC、CB，一共 6 种。这就是排列——选出的两个人按先后（或重要程度）排好顺序。
如果只是选两个人一起去领奖，不分先后：那么AB和BA其实是同一组人，所以只有{AB, AC, BC}这 3 种组合。这就是组合——只关心选出了哪些人，不管顺序。

可以看到：同样的元素个数，排列数总是比组合数多，因为排列把每一种顺序都算成不同的情况。

排列：选人 + 排座位

排列数是指：从 $n$ 个不同的元素中取出 $m$ 个（ $m \leq n$ ），并且把它们按一定顺序排成一排，有多少种不同的排法？用符号 $P(n, m)$ 或 $A(n, m)$ 表示。

公式推导很简单：第一个位置有 $n$ 种选择，第二个位置有 $n-1$ 种选择，……，第 $m$ 个位置有 $n-m+1$ 种选择。根据乘法原理，总数为：

P(n,m) = n \times (n-1) \times \cdots \times (n-m+1) = \frac{n!}{(n-m)!}

生活中的例子：

从5个同学中选2个分别担任班长和副班长： $P(5,2) = 5 \times 4 = 20$ 种。
用数字0-9组成三位密码（数字不重复，且顺序很重要）： $P(10,3) = 10 \times 9 \times 8 = 720$ 种。

组合：选人组成“团”

组合数是指：从 $n$ 个不同的元素中取出 $m$ 个（ $m \leq n$ ），组成一组，不关心内部的顺序，有多少种不同的取法？用符号 $C(n, m)$ 或 $\binom{n}{m}$ 表示。

组合和排列的关系：对于每一种选出的 $m$ 个元素，如果考虑顺序，会有 $m!$ 种不同的排列。因此：

C(n,m) = \frac{P(n,m)}{m!} = \frac{n!}{m!\,(n-m)!}

生活中的例子：

从5个同学中选2个值日生（不分工）： $C(5,2) = \frac{5 \times 4}{2 \times 1} = 10$ 种。
从一副扑克牌中选5张手牌（不关心顺序）： $C(52,5) = 2\,598\,960$ 种。

用 C++ 计算排列与组合

最直接的方法就是写一个计算阶乘的函数，然后套用公式。注意：阶乘增长很快，建议使用 long long 类型（可存到 20! 左右），如果 $n$ 较大需要考虑高精度或使用更聪明的算法（比如边乘边除）。

#include <iostream>
using namespace std;

// 计算阶乘，n! = 1*2*3*...*n
long long factorial(int n) {
    long long result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}

// 排列数 P(n,m) = n! / (n-m)!
long long permutation(int n, int m) {
    if (m > n) return 0;  // 不可能取出超过总数的元素
    return factorial(n) / factorial(n - m);
}

// 组合数 C(n,m) = n! / (m! * (n-m)!)
long long combination(int n, int m) {
    if (m > n) return 0;
    // 直接套公式，但阶乘可能很大，注意溢出
    return factorial(n) / (factorial(m) * factorial(n - m));
}

int main() {
    // 测试：从5个元素中取2个
    int n = 5, m = 2;
    cout << "P(" << n << "," << m << ") = " << permutation(n, m) << endl;  // 输出 20
    cout << "C(" << n << "," << m << ") = " << combination(n, m) << endl;  // 输出 10

    // 再测一组：从10个中选3个
    n = 10; m = 3;
    cout << "P(" << n << "," << m << ") = " << permutation(n, m) << endl;  // 720
    cout << "C(" << n << "," << m << ") = " << combination(n, m) << endl;  // 120
    return 0;
}

运行结果：

P(5,2) = 20
C(5,2) = 10
P(10,3) = 720
C(10,3) = 120

新手容易犯的错误

混淆排列与组合：看到题目先判断“顺序是否重要”。例如：“从3个学生中选2个参加比赛”——组合；如果题目说“选2个分别参加数学和物理比赛”——排列。
忘记条件 m ≤ n：公式在 m > n 时无意义，代码中应返回 0 或提示错误。
整数溢出：直接计算阶乘在 n=21 时就会超过 long long 范围（21! ≈ 5.1×10¹⁹，而 long long 最大值约 9.2×10¹⁸）。对于竞赛题（n ≤ 20）可以放心用，n 更大时要用其他方法，比如用递推公式或边乘边约分。
组合数计算时先算分子再算分母：即使分子和分母都能用 long long 表示，中间结果可能溢出。一个改进方法是利用组合数的递推公式：C(n, m) = C(n-1, m-1) + C(n-1, m)（类似杨辉三角），或者用 for 循环边乘边除：
```
long long combination_opt(int n, int m) {
    if (m > n) return 0;
    if (m > n - m) m = n - m;  // 利用对称性减少计算
    long long result = 1;
    for (int i = 1; i <= m; i++) {
        result = result * (n - i + 1) / i;  // 先乘后除，保证整除
    }
    return result;
}
```
这样可以用 long long 处理更大的 n（比如 n=60 左右还安全）。

完整示例：一个交互式程序

下面提供一个完整的交互式程序，让用户输入 n 和 m，然后输出排列数和组合数。它包含了对 m > n 的检查，以及使用优化后的组合函数（防止溢出）。

#include <iostream>
using namespace std;

// 计算阶乘（n较小且安全时使用）
long long factorial(int n) {
    long long res = 1;
    for (int i = 2; i <= n; i++) res *= i;
    return res;
}

// 排列数：P(n,m)
long long permutation(int n, int m) {
    if (m > n) return 0;
    return factorial(n) / factorial(n - m);
}

// 组合数（优化版，避免大阶乘溢出）
long long combination(int n, int m) {
    if (m > n) return 0;
    // 利用 C(n,m) = C(n, n-m) 来减少循环次数
    if (m > n - m) m = n - m;
    long long result = 1;
    for (int i = 1; i <= m; i++) {
        result = result * (n - i + 1) / i;  // 每次乘一个数，除一个数，确保整除
    }
    return result;
}

int main() {
    cout << "请输入 n 和 m（n >= m >= 0，建议 n <= 60）：";
    int n, m;
    cin >> n >> m;

    if (m < 0 || n < 0 || m > n) {
        cout << "输入不合法：请确保 n >= m >= 0" << endl;
        return 1;
    }

    cout << "P(" << n << "," << m << ") = " << permutation(n, m) << endl;
    cout << "C(" << n << "," << m << ") = " << combination(n, m) << endl;
    return 0;
}

运行示例：

请输入 n 和 m（n >= m >= 0，建议 n <= 60）：10 3
P(10,3) = 720
C(10,3) = 120

排列与组合——选顺序还是选“团”