第61章 计数原理

计数原理是组合数学的基础，主要研究完成一件事的不同方法的数量计算规则。八级考试中，它常与排列组合、杨辉三角结合出题，是方案统计、组合数计算的底层工具。

61.1 基本计数原理

61.1.1 加法原理(分类计数原理)

定义 若完成一件事有$n$类不同的方法，在第1类方法中有$m_1$种不同的方式，在第2类方法中有$m_2$种不同的方式……在第n类方法中有$m_n$种不同的方式，且这些方法彼此独立（即选择任何一类方法中的任何一种方式都能单独完成这件事），则完成这件事的$总方法数 = m_{1} × m_{2} × ... × m_{n} = m_{1}+m_{2}+...+m_{n}$为各类方法数之和： $总方法数 = m_{1} × m_{2} × ... × m_{n} = m_{1}+m_{2}+...+m_{n} = m_{1}+m_{2}+...+m_{n}$ 核心特征

1. "分类"：各类方法之间是"或"的关系。
2. "互斥"：不同类的方法不能同时使用。

示例 从 A 地到B地，可乘火车、汽车或飞机。火车有3班次，汽车有5班次，飞机有2班次，则从A地到B地的总交通方式有 $3+5+2=10$ 种。

61.1.2 乘法原理(分步计数原理)

定义 若完成一件事需要经过$n$个步骤，完成第1步有$m_1$种不同的方式，完成第2步有$m_2$种不同的方式……完成第n步有$m_n$种不同的方式，且各步骤之间相互依赖（只有完成所有步骤才能完成这件事），则完成这件事的$总方法数 = m_{1} × m_{2} × ... × m_{n} = m_{1}+m_{2}+...+m_{n}$为各步骤方法数的乘积： $总方法数 = m_{1} × m_{2} × ... × m_{n} = m_{1}+m_{2}+...+m_{n} = m_{1} × m_{2} × ... × m_{n}$ 核心特征

1. "分步"：各步骤之间是"且"的关系。
2. "关联"：前一步骤的选择会影响后一步骤的可选项，但不影响方法数的计算。

示例 从 A 地到B地需先乘火车到C地，再乘汽车到B地。从 A 到C的火车有3班次，从C到B的汽车有5班次，则从A地到B地的总交通方式有 $3 ×5=15$ 种。

61.1.3 加法原理与乘法原理的区别

61.2 排列

61.2.1 定义

排列是指从 n 个不同元素中，取出 k 个元素 $(1 ≤k ≤n)$，按照一定的顺序排成一列，称为从 $n$ 个不同元素中取出k个元素的一个排列。所有可能的排列的数量称为排列数，记作 $P(n, k)$或 $A(n, k)$。

61.2.2 计算公式

排列数公式： $P(n, k)=n \times(n-1) \times(n-2) × \cdots \times(n-k+1)$ 阶乘表示：由于 $n! =n \times(n-1) ×\cdots ×1$（$n$的阶乘），排列数可表示为： $P(n, k)=\frac{n !}{(n-k) !}$ 规定 $0 !=1$，当 $k=n$ 时，$P(n, n)=n !$。

61.2.3 示例

从5名同学中选3人站成一排拍照，不同的排列方式有： $P(5,3)=5 ×4 ×3=60$ 种。 3个不同的数字全排列 $(k=n=3)$：$P(3,3)=3 !=6$ 种（即123、132、213、231、312、321）。

61.2.4 关键特征

有序性：排列中元素的顺序不同则视为不同的排列（如 "ab" 与 "ba" 是两个不同的排列）。 无重复：取出的k个元素必须互不相同。

61.3 组合

61.3.1 定义

组合是指从n个不同元素中，取出k个元素 $(1 ≤k ≤n)$，不考虑元素的顺序组成一组，称为从 n 个不同元素中取出k个元素的一个组合。所有可能的组合的数量称为组合数，记作 $C(n, k)$。

61.3.2 计算公式

组合数与排列数的区别在于"无序"，因此组合数等于排列数除以 k 个元素的全排列数： $C(n, k)=\frac{P(n, k)}{P(k, k)}=\frac{n !}{k ! \times(n-k) !}$ 性质：

1. $C(n, k)=C(n, n-k)$
2. $C(n, 0)=1$，$C(n, n)=1$

61.3.3 示例

从5名同学中选3人参加座谈会，不同的选法有： $C(5,3)=\frac{5 !}{3 ! × 2 !}=\frac{5 × 4 × 3}{3 × 2 × 1}=10$ 种。 从4个元素中选2个的组合数： $C(4,2)=6$ 种（ab、ac、ad、bc、bd、cd）。

61.3.4 关键特征

无序性：组合中元素的顺序不影响结果（如"ab"与"ba"是同一个组合）。 无重复：取出的k个元素必须互不相同。

61.4 排列与组合的区别

61.5 常见计数场景与技巧

61.5.1 有限制条件的计数

特殊元素优先法 当某些元素有特殊位置要求时，先安排特殊元素，再处理其他元素。 示例：用09这10个数字组成无重复数字的三位数，百位不能为0。 解法：先选百位（9种选择：19），再选十位9种选择，最后选个位8种选择，总个数为 $9 ×9 ×8=648$。

排除法 先计算无限制条件的$总方法数 = m_{1} × m_{2} × ... × m_{n} = m_{1}+m_{2}+...+m_{n}$，再减去不符合条件的方法数。 示例：从5名同学中选3人参加活动，甲不能参加。 解法：总选法 $C(5,3)=10$，甲必选的选法 $C(4,2)=6$，符合条件选法 $10-6=4$。

61.5.2 可重复元素的计数

可重复排列：从 $n$ 个不同元素中取出k个，允许重复，排列数 $n^k$。 示例：3位数字密码，每位0~9，总数 $10^3=1000$。

可重复组合：从 $n$ 个不同元素取k个可重复，组合数 $C(n+k-1, k)$。 示例：5个相同苹果分给3个小朋友，分法 $C(5+3-1,5)=C(7,5)=21$。

61.5.3 分步与分类综合应用

先分类，每一类内部分步计算，最后用加法汇总。 示例：A到B可选飞机(2)、火车(3)、汽车(5)；B到C火车4或汽车6。 飞机路线：$2 \times (4+6)=20$ 火车路线：$3 \times (4+6)=30$ 汽车路线：$5 \times (4+6)=50$ 总方式：$20+30+50=100$

61.6 计数原理在编程中的应用

适用场景：算法复杂度计算、排列组合求值、概率统计。

61.6.1 C++代码（阶乘、排列、组合）

#include<iostream>
using namespace std;

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

//计算排列 P(n, k)
long long permutation(int n, int k) {
    if (k<0 || k>n) return 0;
    long long res=1;
    for (int i=0;i<k;++i){
        res*=(n -i);
    }
    return res;
}

//计算组合 C(n, k)
long long combination(int n, int k){
    if (k<0 || k>n) return 0;
    if (k>n-k) k=n-k;
    long long res=1;
    for (int i=1;i<=k; ++i) {
        res=res*(n-k+i)/i;
    }
    return res;
}

int main(){
    cout <<"5! = "<< factorial(5) << endl;
    cout <<"P(5, 3) = "<< permutation (5, 3) << endl;
    cout << "C(5, 3)="<< combination(5, 3) <<endl;
    return 0;
}

## 61.7 真题示例（全排列生成）

> **【GESP 八级风格·编程题】**
> **题目描述**：输入整数 $$n$$（$$1 \le n \le 8$$），按字典序输出 $$1$$ 到 $$n$$ 的所有全排列，每个排列一行，数字之间用空格隔开。
> **输入格式**：一行一个整数 $$n$$。
> **输出格式**：所有排列，每行一个。
> **样例输入**：`3`
> **样例输出**：
> ```
> 1 2 3
> 1 3 2
> 2 1 3
> 2 3 1
> 3 1 2
> 3 2 1
> ```

**参考解答（回溯法，直观体现"排列 = 逐位选择未用过的数"）：**

```cpp
#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> path;        // 当前排列
vector<bool> used;       // 数字是否已被选

void dfs(int depth) {
    if (depth == n) {                    // 已选满 n 位
        for (int i = 0; i < n; ++i)
            cout << path[i] << (i == n - 1 ? "" : " ");
        cout << "\n";
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {                  // 只选没用过的数字 → 保证"无重复"
            used[i] = true;
            path.push_back(i);
            dfs(depth + 1);               // 递归选下一位（分步）
            path.pop_back();              // 回溯
            used[i] = false;
        }
    }
}

int main() {
    cin >> n;
    used.assign(n + 1, false);
    dfs(0);
    return 0;
}

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) a[i] = i + 1;
    do {
        for (int i = 0; i < n; ++i) cout << a[i] << (i == n - 1 ? "" : " ");
        cout << "\n";
    } while (next_permutation(a.begin(), a.end()));
    return 0;
}

练习题

1.（原理） 从甲地到乙地可乘火车（3 班）、汽车（4 班）或飞机（2 班），任意选一种交通方式即可到达。共有多少种走法？

• A. 9
• B. 24
• C. 6
• D. 12

2.（排列/组合） 从 5 名不同的同学中选出 3 人组成一组参加会议，不同的选法有多少种？

• A. $P(5,3)=60$
• B. $C(5,3)=10$
• C. $5^3=125$
• D. $3^5=243$

3.（受限计数） 用数字 1~9 组成没有重复数字的三位数，共有多少个？

• A. $9 \times 9 \times 8 = 648$
• B. $9 \times 8 \times 7 = 504$
• C. $10 \times 9 \times 8 = 720$
• D. $9^3 = 729$

4.（可重复） 一个 3 位密码锁，每位可以是 0~9 中任意一个数字且允许重复，共有多少种密码？

• A. $P(10,3)=720$
• B. $C(10,3)=120$
• C. $10^3=1000$
• D. $10\times9\times8=720$

5.（全排列） 4 个不同的字母排成一排，共有多少种排法？

• A. 12
• B. 16
• C. 24
• D. 4