计数篇 —— 排列组合与杨辉三角

# 计数篇——排列组合与杨辉三角

引入

从 3 个同学里选 2 个值日，有几种选法？是 3 种（甲乙、甲丙、乙丙）。这类「从一堆里选几个、或排几个」的问题，就是排列组合，是 CSP-J 初赛和 GESP 的高频考点。而杨辉三角能帮你快速算出组合数，不用硬背公式。

---

一、排列与组合

1. 排列（有序）：A

从 n 个不同元素中选 m 个，排成一列（顺序不同算不同）：


A(n, m) = n × (n-1) × ... × (n-m+1)

例：从 4 个人中选 2 个排成前后两排：A(4,2) = 4×3 = 12。

2. 组合（无序）：C

从 n 个不同元素中选 m 个，组成一组（顺序不同算同一种）：


C(n, m) = A(n, m) / m! = n! / (m! × (n-m)!)

例：从 4 个人中选 2 个去值日：C(4,2) = (4×3)/(2×1) = 6。

3. 关键区别

> 排列看重顺序（排位置），组合不看重顺序（选一组）。判断一句「选的人站不站队」就能区分。

4. 常用性质

C(n, 0) = C(n, n) = 1
对称性：C(n, m) = C(n, n-m)
递推公式（组合数递推）：C(n, m) = C(n-1, m-1) + C(n-1, m)

---

二、杨辉三角（帕斯卡三角）

把上面的递推公式画出来，就得到杨辉三角：

1 1

1 2 1

1 3 3 1

1 4 6 4 1

第 n 行（从 0 开始）的第 m 个数就是 C(n, m)。
每个数 = 它左上方 + 右上方两个数之和（就是递推公式）。
例：第 4 行 1 4 6 4 1，对应 C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4)=1。

代码：用递推求组合数

cpp
long long C[31][31];          // C[n][m]
void init() {
    for (int i = 0; i <= 30; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];   // 递推
    }
}

---

三、CSP 常考的计数模型

加法原理 / 乘法原理：互斥用加，分步用乘。
捆绑法：要求相邻的，先捆一起当整体排，再排内部。
插空法：要求不相邻的，先排其余，再把它们插进空隙。
容斥原理：|A∪B| = |A|+|B|-|A∩B|。
错排 / 环形排列：n 个元素环排是 (n-1)!。
二项式定理：(a+b)^n 展开第 m+1 项系数就是 C(n,m)，杨辉三角就是它的系数表。

---

四、考点提示

选择题常问「从…选…有几种」：先分清排列还是组合，再套公式或用杨辉三角递推。
代码完善题常把杨辉三角递推、组合数表初始化作为填空。
陷阱：问的是「含某元素 / 不含某元素」，先分类再乘。

一句话记忆：排列讲顺序用 A，组合讲选择用 C；杨辉三角每一行就是一组组合数，递推公式 C(n,m)=C(n-1,m-1)+C(n-1,m)。