从排队选班长到游戏抽卡：搞懂排列与组合就能轻松计数

咱们生活中经常会遇到这样的问题：班里有30个同学，要选一个班长和一个副班长，有多少种选法？如果只是选两个人去参加学校的演讲比赛，又有多少种选法？为什么第一个问题的答案比第二个多很多？秘密就在于——顺序重不重要。

排列（Permutation）和组合（Combination）是组合数学里最基础、最常用的两个工具。简单说：如果选出来的东西有先后顺序（比如班长和副班长不一样），那就是排列问题；如果选出来的东西不分先后（比如两个普通代表），那就是组合问题。学好了它，你就能轻松解决各种“选人”“排座位”“抽奖”“游戏搭配”的问题，而且在编程竞赛中也经常出现。

下面咱们从生活例子入手，一步步搞懂公式、性质，再学会用C++和Python程序计算它们。

排列：排队、列队、顺序有影响。
组合：合在一起、团队、谁先谁后无所谓。

2. 排列（Permutation）：有顺序的计数

2.1 定义和公式

从 n 个不同的东西里，挑出 m 个（m ≤ n），按一定顺序排成一列，有多少种不同的排法？这个数目记作 P(n, m)（有些书也写成 A(n, m)）。

计算公式：

P(n, m) = n \times (n-1) \times (n-2) \times \cdots \times (n-m+1)

也可以写成阶乘形式：

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

如果 m = n，也就是把 n 个东西全部排成一列，就叫全排列：

P(n, n) = n!

2.2 生活中的例子

书架摆书：你有5本不同的书，想选3本摆在书架的架子上，顺序不同看起来就不一样（比如第一本是《哈利·波特》还是《三体》不同）。摆法有 P(5,3) = 5×4×3 = 60 种。
班级照相：3个同学排成一排拍照，有多少种站法？全排列 3! = 3×2×1 = 6 种。
密码设置：用数字1、2、3组成一个3位数，每个数字只能用一次，可以组成多少个不同的3位数？就是全排列 3! = 6个（123,132,213,231,312,321）。
游戏角色：你有4个英雄，想选出3个组成一个“出场顺序阵容”（比如第一个攻击，第二个辅助，第三个防御），阵容因顺序不同而不同，那就是 P(4,3) = 4×3×2 = 24 种。

2.3 为什么公式是连乘？——一个简单推导

想象你是一个“排座位”的队长：

第一个位置：你有 n 个人可以选，所以有 n 种可能。
第二个位置：已经用掉1个人，还剩 n-1 个人可选，所以有 n-1 种可能。
第三个位置：还剩 n-2 个人可选……
直到第 m 个位置：还剩 n-m+1 个人可选。

根据乘法原理，把每一步的选择数乘起来，就得到 P(n, m) = n×(n-1)×…×(n-m+1)。

3. 组合（Combination）：无顺序的计数

3.1 定义和公式

从 n 个不同的东西里，挑出 m 个（m ≤ n），只管选出来，不管顺序，有多少种挑法？这个数目记作 C(n, m)（也读作“n选m”）。

计算公式：

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

3.2 生活中的例子

借书：你有5本不同的书，想选3本借给朋友，朋友回家随便看，不在乎你给书的顺序。所以选法只有 C(5,3) = 5×4×3 ÷ (3×2×1) = 10 种（而不是60种）。
选代表：全班30人选2名同学参加学校大会，不计顺序。选法有 C(30,2) = 30×29÷2 = 435 种。
抽奖：一个袋子里有10个不同的奖品，抽3个给同一个人，这个人拿到哪三个不在乎次序，所以中奖组合有 C(10,3) = 120 种。
分组：从6个好朋友中选2个人一起去食堂吃饭，有多少种不同的小团体？C(6,2) = 15 种。

3.3 排列和组合的关系：先排再删掉顺序

为什么组合数等于排列数除以 m!？因为：

先按排列来想：从n个中挑出m个并排成顺序，有 P(n, m) 种。
但组合不关心顺序，这 m 个元素的所有不同排列（有 m! 种）在组合里都算同一种选法。
所以组合数 = 排列数 ÷ 所有排列的种数 = P(n, m) / m!

例如：从{A, B, C}中选2个元素，排列有：AB, BA, AC, CA, BC, CB 共6种。但组合只看集合：{A,B}, {A,C}, {B,C} 共3种。3 = 6 ÷ 2!（2! = 2）。

4. 组合数的几个好用的性质

这些性质在手工计算和编程中都非常有用：

C(n, 0) = 1：啥也不选，只有一种方式（就是空手）。
C(n, n) = 1：全选，也只有一种方式。
对称性：C(n, m) = C(n, n-m)
比如 C(10, 3) = C(10, 7) 都是120。因为从10个里选3个留下，等价于选7个扔掉。
帕斯卡恒等式（递推公式）： $C(n, m) = C(n-1, m-1) + C(n-1, m)$ 这个公式很有用，可以像搭积木一样从小的数推出大的数，也是杨辉三角（二项式系数表）的构造原理。

5. 编程实现：用C++和Python计算排列与组合

直接套用阶乘公式虽然简单，但 n! 增长非常快（20! ≈ 2.4×10¹⁸，64位整数就装不下了）。所以我们需要更聪明的方法，比如：

递推法：用帕斯卡三角形建表，适合n不大（比如n≤100）且需要多次查询的情况。
迭代乘法：边乘边除，保持结果在整数范围内，避免大数溢出。

下面给出三种方法的代码，注意每行变量都加上了中文注释。

C++ 代码

#include <iostream>
using namespace std;

// 方法1：直接套公式（仅适用于n很小，例如n≤20）
// 计算阶乘的函数
long long factorial(int n) {
    long long res = 1;             // 结果初始为1
    for (int i = 2; i <= n; i++) {
        res = res * i;             // 依次乘以2,3,...,n
    }
    return res;
}

// 排列数 P(n, m)
long long permutation_formula(int n, int m) {
    return factorial(n) / factorial(n - m);
}

// 组合数 C(n, m)
long long combination_formula(int n, int m) {
    return factorial(n) / (factorial(m) * factorial(n - m));
}

// 方法2：递推法（帕斯卡三角形），适合n≤100且需要多次查询
const int MAXN = 100;             // 最大n值
long long C[MAXN+1][MAXN+1];     // 二维数组存储所有C[i][j]

// 初始化组合数表，计算所有C[i][j] (0≤j≤i≤n)
void init_combinations(int n) {
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;              // C(i,0)=1
        C[i][i] = 1;              // C(i,i)=1
        for (int j = 1; j < i; j++) {
            // 帕斯卡恒等式：C(i,j) = C(i-1,j-1) + C(i-1,j)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
}

// 方法3：迭代乘法（边乘边除），效率高且不易溢出
long long combination_iter(int n, int m) {
    // 利用对称性，取较小的m减少计算量
    if (m > n - m) {
        m = n - m;                 // 比如C(10,7)变成C(10,3)
    }
    long long result = 1;          // 结果初始为1
    for (int i = 1; i <= m; i++) {
        // 每次乘以 (n - m + i) 再除以 i，保证每一步结果都是整数
        result = result * (n - m + i) / i;
    }
    return result;
}

int main() {
    int n = 10, m = 3;
    cout << "P(" << n << "," << m << ") = " << permutation_formula(n, m) << endl;
    cout << "C(" << n << "," << m << ") = " << combination_formula(n, m) << endl;

    // 使用递推表
    init_combinations(10);
    cout << "C(10,3) 递推 = " << C[10][3] << endl;

    // 使用迭代乘法
    cout << "C(10,3) 迭代 = " << combination_iter(10, 3) << endl;
    return 0;
}

Python 代码

import math

# 方法1：直接使用math库的阶乘函数
def permutation(n, m):
    """计算排列数 P(n, m)"""
    return math.factorial(n) // math.factorial(n - m)

def combination(n, m):
    """计算组合数 C(n, m)"""
    return math.factorial(n) // (math.factorial(m) * math.factorial(n - m))

# 方法2：递推法构建组合数表（杨辉三角）
def build_comb_table(limit):
    """
    生成一个 (limit+1) x (limit+1) 的二维列表，存储所有C[i][j]
    limit: 最大的n值
    """
    C = [[0] * (limit + 1) for _ in range(limit + 1)]  # 全部初始化为0
    for i in range(limit + 1):
        C[i][0] = 1          # C(i,0)=1
        C[i][i] = 1          # C(i,i)=1
        for j in range(1, i):
            C[i][j] = C[i-1][j-1] + C[i-1][j]   # 帕斯卡恒等式
    return C

# 方法3：迭代乘法（边乘边除），推荐使用
def combination_iter(n, m):
    """计算组合数 C(n, m)，使用迭代乘法避免大数溢出"""
    if m > n - m:            # 利用对称性，让m尽量小
        m = n - m
    result = 1               # 结果初始为1
    for i in range(1, m + 1):
        # 每次乘以 (n - m + i) 再除以 i，保证整数
        result = result * (n - m + i) // i
    return result

# 测试
n, m = 10, 3
print("P({},{}) = {}".format(n, m, permutation(n, m)))   # 720
print("C({},{}) = {}".format(n, m, combination(n, m)))   # 120

# 使用递推表
C_table = build_comb_table(10)
print("C(10,3) 递推 =", C_table[10][3])                  # 120

# 使用迭代乘法
print("C(10,3) 迭代 =", combination_iter(10, 3))         # 120

输出结果

P(10,3) = 720
C(10,3) = 120
C(10,3) 递推 = 120
C(10,3) 迭代 = 120

6. 完整例子：抽奖问题（输入输出）

编写一个程序，让用户输入 n 和 m，然后输出 P(n,m) 和 C(n,m)。这里我们用Python的迭代乘法（最安全）来实现。

def combination_iter(n, m):
    if m > n - m:
        m = n - m
    result = 1
    for i in range(1, m + 1):
        result = result * (n - m + i) // i
    return result

def permutation_iter(n, m):
    # 排列也可以用迭代：n*(n-1)*...*(n-m+1)
    result = 1
    for i in range(m):
        result *= (n - i)
    return result

# 输入
n = int(input("请输入总物品数 n："))
m = int(input("请输入选取个数 m："))

# 计算并输出
if m > n:
    print("错误：m不能大于n！")
else:
    print("排列数 P({},{}) = {}".format(n, m, permutation_iter(n, m)))
    print("组合数 C({},{}) = {}".format(n, m, combination_iter(n, m)))

运行示例：

请输入总物品数 n：10
请输入选取个数 m：3
排列数 P(10,3) = 720
组合数 C(10,3) = 120

7. 新手最容易犯的5个错误

混淆排列和组合
看到“选人”就以为是组合，忘了题目里有没有“职务”“顺序”等字眼。关键：题目中是否强调顺序？ 比如“站成一排”“做标记”“编号”等往往是有序。
例：从5个同学中选3个打扫卫生（不计顺序）→ 组合；选3个分别负责扫地、拖地、倒垃圾 → 排列。
忘记 m=0 的情况
当 m=0 时，排列和组合都等于 1（什么都不选只有一种方法）。很多程序里要单独处理，或者确保循环条件正确。
直接算阶乘导致溢出
在C++中，long long最多只能存到 20! 左右。n=21时就会爆掉。解决：用递推或迭代乘法。
递推时数组越界
比如在C++中，C[i][j] 访问时确保 j ≤ i，否则会访问到未初始化的值或越界。
把组合数公式写成 P(n,m)/m 而不是除以 m!
一个常见的笔误是只除以 m 而不是阶乘，导致结果偏大。

8. 练一练（答案在文末）

选队长：从6名同学中选3人参加数学竞赛，有多少种选法？如果3人分别担任队长、副队长、队员（职务不同），又有多少种安排？
数字密码：用数字 1,2,3,4,5 可以组成多少个没有重复数字且大于40000的五位数？
游戏装备：你有8件不同的装备，想选4件穿在身上，但装备有“头盔、上衣、裤子、鞋子”四个部位（顺序重要），有多少种搭配？如果只是随便带4件出门（不分部位），有多少种带法？

答案

选代表（组合）：C(6,3) = 20种；选职务（排列）：P(6,3) = 120种。
大于40000的五位数，首位只能是4或5（2种选择），剩下4位全排列 4! = 24，总共 2×24 = 48个。
分部位（排列）：P(8,4) = 8×7×6×5 = 1680种；不分部位（组合）：C(8,4) = 70种。

9. 小结与延伸

排列和组合是计数的核心工具。记住：

排列=有序，组合=无序。
公式要记住，但更重要的是判断题目是哪种。
编程实现时优先选用递推或迭代法，避免直接算阶乘。

掌握了排列组合，你还可以进一步学习：

二项式定理：(a+b)^n 展开后的系数就是组合数。
概率计算：很多概率题都要先算排列/组合的总数。
鸽巢原理、容斥原理等更高级的计数技巧。
动态规划中的组合数递推：比如背包问题里常用组合数思想。

希望你以后遇到“选人、排座位、抽奖、游戏抽卡”等问题时，能一眼看出是排列还是组合，并且轻松用代码算出来！

排列与组合的概念与计算