排列组合

排列组合是计数问题的核心，也是容斥原理、概率、动态规划等的基础。核心就一句话：数清楚有多少种情况。

一、加法原理与乘法原理

1.1 加法原理（分类）

完成一件事，有几种独立、互斥的方法（用了这种就不能用那种），总方法数 = 各方法数相加。

例：从 A 城到 B 城，可以坐火车（3 个班次）或坐飞机（2 个班次）。

坐火车和坐飞机是互斥的两种方式，总走法 = $3 + 2 = 5$ 种。

1.2 乘法原理（分步）

完成一件事，需要分几步做（每一步都要做），总方法数 = 各步方法数相乘。

例：从 A 到 B 有 3 条路，从 B 到 C 有 2 条路，从 A 到 C 要经过 B。

分两步（先 A→B，再 B→C），总走法 = $3 \times 2 = 6$ 种。

1.3 怎么区分

	加法原理	乘法原理
关键词	要么…要么…	先…再…
本质	分类，互斥	分步，都要做
运算	相加	相乘

💡 口诀：分类相加，分步相乘。

二、排列组合

2.1 定义

从 n 个不同元素中，选出 k 个（ $k \le n$ ）。

2.2 排列与组合的区别

	排列	组合
是否看顺序	有顺序（要排队）	无顺序（选出一组）

例：从 A、B、C 三个人里选 2 个：

排列（有顺序）：AB、BA、AC、CA、BC、CB，共 6 种
组合（无顺序）：AB、AC、BC，共 3 种

💡 判断：把选出的元素调换顺序，如果算新的结果，就是排列；不算，就是组合。

2.3 排列数 A(n,k)

从 n 个不同元素里选 k 个排成一排的方法数，记作 $A(n,k)$ （也写作 $P(n,k)$ ）。

推导（用乘法原理）：

第 1 个位置：有 $n$ 种选法；
第 2 个位置：用掉 1 个，剩下 $n-1$ 种选法；
第 3 个位置：剩下 $n-2$ 种；
……
第 k 个位置：剩下 $n-k+1$ 种。

用乘法原理相乘：

$A(n,k) = n \times (n-1) \times (n-2) \times \cdots \times (n-k+1)$

这是 k 个连续的数相乘（从 n 一直乘到 n-k+1，共 k 个）。

为什么要化简：直接写 $n \times (n-1) \times \cdots \times (n-k+1)$ 太啰嗦（k 很大时尤其麻烦），化成阶乘形式更简洁、好记。

化简成阶乘（分子补成阶乘）：上面的乘积已经是从 n 乘到 n-k+1，缺的是从 n-k 乘到 1 这部分。分子、分母同时乘上缺的那部分，值不变：

$A(n,k) = \frac{n \times (n-1) \times \cdots \times (n-k+1) \times (n-k) \times \cdots \times 2 \times 1}{(n-k) \times \cdots \times 2 \times 1}$

分子现在从 n 一直乘到 1，就是 $n!$ ；分母从 n-k 一直乘到 1，就是 $(n-k)!$ 。所以：

$A(n,k) = \frac{n!}{(n-k)!}$

具体例子： $A(7,3) = 7 \times 6 \times 5$

分子 $7 \times 6 \times 5$ 缺了 $4 \times 3 \times 2 \times 1$ ，补上：

$A(7,3) = 7 \times 6 \times 5 = \frac{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{4 \times 3 \times 2 \times 1} = \frac{7!}{4!} = \frac{7!}{(7-3)!}$

2.4 全排列

n 个元素全部排列，等价于 n 选 n：

$A(n,n) = n! = n \times (n-1) \times \cdots \times 2 \times 1$

为什么是 n!：用乘法原理——第 1 个位置有 $n$ 种选法，第 2 个位置剩下 $n-1$ 种，第 3 个位置剩下 $n-2$ 种，……，最后一个位置只剩 1 种。

演示例子：A、B、C 三个元素的全排列。

第 1 个位置：3 种（放 A 或 B 或 C）
第 2 个位置：剩下 2 种
第 3 个位置：剩下 1 种

共 $3 \times 2 \times 1 = 6$ 种。全部列出来：

第 1 位固定 A：剩下 B、C 排 → ABC、ACB （2 种）  
第 1 位固定 B：剩下 A、C 排 → BAC、BCA （2 种）  
第 1 位固定 C：剩下 A、B 排 → CAB、CBA （2 种）

一共 $3 \times 2 = 6$ 种，即 $3! = 6$ 。

💡 全排列就是排列数 $A(n,k)$ 当 $k=n$ 时的特例。

2.5 组合数 C(n,k)

从 n 个不同元素里选 k 个（不管顺序）的方法数，记作 $C(n,k)$ 或 $\binom{n}{k}$ 。

推导（基于排列数）：先想清楚组合和排列的关系。

组合：从 n 个里选出一组 k 个，这 k 个之间没有先后顺序；
排列：先选出 k 个，再把这 k 个排成一排（有顺序）。

所以「先组合、再排列」就等于排列数：

$A(n,k) = C(n,k) \times k!$

为什么要除以 k!：同一个组合里的 k 个元素，能排成 $k!$ 种不同的顺序——也就是一个组合会被重复算 $k!$ 次。把排列数除以 $k!$ ，就消除了这种重复。

代入排列数，得到：

$C(n,k) = \frac{A(n,k)}{k!} = \frac{n!}{k!\,(n-k)!}$

具体例子：从 A、B、C、D 4 个里选 3 个。

组合有 $C(4,3) = 4$ 个：{A,B,C}、{A,B,D}、{A,C,D}、{B,C,D}；
每个组合里的 3 个元素能排成 $3! = 6$ 种排列，比如 {A,B,C} 能排成 ABC、ACB、BAC、BCA、CAB、CBA；
所以排列数 = 4 个组合 × 6 种顺序 = $24 = A(4,3)$ ；
反过来，组合数 = 排列数 ÷ 3! = $24 \div 6 = 4 = C(4,3)$ 。

例： $C(5,3) = \dfrac{5 \times 4 \times 3}{3 \times 2 \times 1} = 10$

💡 常用性质： $C(n,k) = C(n, n-k)$ （选 k 个等价于剩下 n-k 个）。

三、排列组合应用

3.1 捆绑法（元素必须相邻）

某些元素必须相邻，先把它们绑成一个整体，再和其他元素一起排列。

例：甲乙丙 3 人排一排，甲乙必须相邻。

把甲乙绑成一个整体，相当于 2 个"元素"（甲乙整体、丙）全排列：

$\underbrace{2!}_{\text{整体排列}} \times \underbrace{2!}_{\text{甲乙内部}} = 4$

[甲乙] 丙 →   2 种整体排列  
 甲乙 / 乙甲 →   2 种内部排列

3.2 插空法（元素不相邻）

某些元素不能相邻，先排其他元素，再把不相邻的元素插到空位里。

例：3 男 2 女排一排，女生不能相邻。

先排 3 男： $3! = 6$ 种。排好后有 4 个空位：

_ 男 _ 男 _ 男 _

4 个空位选 2 个放女生： $A(4,2) = 4 \times 3 = 12$ 种。

$3! \times A(4,2) = 6 \times 12 = 72$

3.3 隔板法（相同物品分给若干组）

把 n 个相同物品分给 k 个组，用 $k-1$ 个隔板把物品隔成 k 份。分两种情况：不允许空和允许空。

（1）不允许空（每组至少一个）

n 个球排成一排，中间有 $n-1$ 个空隙。用 $k-1$ 个隔板插进空隙，把球分成 k 份，每份至少 1 个球。

方法数： $C(n-1, k-1)$

例：10 个相同的球分给 3 个盒子，每盒至少一个。

10 个球有 9 个空隙，选 2 个放隔板：

○ ○ | ○ ○ ○ | ○ ○ ○ ○ ○

$C(9,2) = 36$

（2）允许空（盒子可以为空）

如果允许空，隔板可能相邻，甚至出现在两端，不能直接用"插空隙"。

技巧：先给每个盒子预放一个球，把"允许空"转成"不允许空"：

先给 k 个盒子各预放 1 个球（共 k 个虚拟球），球数从 n 变成 $n+k$ ；
现在要求"每盒至少一个"，用隔板法： $C((n+k)-1, k-1) = C(n+k-1, k-1)$ ；
最后把虚拟球拿掉，就得到允许空的分法。

例：10 个相同的球分给 3 个盒子，允许盒子为空。

先给 3 个盒各预放 1 个球，变成 13 个球，要求每盒至少一个：

○ ○ ○ | ○ ○ ○ ○ | ○ ○ ○ ○ ○ ○  
（拿掉预放的 3 个虚拟球后，就是允许空的一种分法）

$C(12,2) = 66$

💡 对比记：不允许空是 $C(n-1, k-1)$ ，允许空是 $C(n+k-1, k-1)$ ——允许空就是先塞 k 个虚拟球，球数从 n 变成 n+k，再按"至少一个"算。

四、容斥原理

4.1 集合概念

概念	符号	含义
并集	$A \cup B$	属于 A 或属于 B 的元素
交集	$A \cap B$	同时属于 A 和 B 的元素

4.2 容斥原理

容斥原理是干什么的：数并集的大小——也就是"至少满足一个条件"的元素有多少个。

从一个例子开始：一个班的学生参加社团，人数如下：

情况	人数
参加数学社团	20
参加英语社团	15
参加编程社团	12
同时参加数学和英语	5
同时参加英语和编程	4
同时参加数学和编程	3
三个都参加	2

问：至少参加了一个社团的，一共多少人？

错误算法：直接 $20 + 15 + 12 = 47$ 人。但这样把"同时参加多个社团"的人重复算了。

正确算法：

先加三个单社团： $20 + 15 + 12 = 47$ ；
"同时参加两个社团"的人被算了两次，减掉两两交集： $47 - 5 - 4 - 3 = 35$ ；
"三个都参加"的 2 人，刚才被加了 3 次、又减了 3 次（等于没算），加回来： $35 + 2 = 37$ 。

所以总人数 = 37 人。

抽象成公式（三个集合 A、B、C）：

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

💡 规律：先加单集、再减两两交集、最后加三交集——交替加减。本质是「数并集会重复，多算的减掉，减过头的加回来」。

两个集合（更简单的情况）：

$|A \cup B| = |A| + |B| - |A \cap B|$

再来一个数字例子：1 到 100 中，能被 3 或 5 整除的数有多少个？

设 A = 能被 3 整除的数，B = 能被 5 整除的数，求 $|A \cup B|$ 。

$|A| = \lfloor 100/3 \rfloor = 33$ 个
$|B| = \lfloor 100/5 \rfloor = 20$ 个
$|A \cap B|$ = 同时被 3 和 5 整除（即 15 的倍数）= $\lfloor 100/15 \rfloor = 6$ 个

$|A \cup B| = 33 + 20 - 6 = 47$

如果不减交集，会得到 53——因为同时被 3 和 5 整除的 6 个数被算了两次。