排列组合非常神奇

---

一.计数方法

1.加法原理：

例子: 比如一个问题有n中情况,每里有$m_i$种方法，so总方法数为：$m_1$ + $m_2$ + ... + $m_n$种方法。

2.乘法原理：

例子: 一只小波鼠要走到a[$n$]，后走到a[$i$]需$m_i$步，一共需要$m_1$ * $m_2$ * ... * $m_n$步

---

二.基础概念与公式

1.排列($Permutation$)：

定义： 从$n$个数据中选$m$个数据按照 顺序 排队叫排列。记作$P^m_n$。

$公式$

$$P^m_n=A^m_n=\frac{n!}{(n-m)!}$$

‌全排列: $P^n_n$ = $n!$

例子: 3人排队有$P^3_3$ = $3!$ = 6种方案

2.组合 ($Combination$)：

定义: 从 $n$ 个元素中取 $m$个元素‌不考虑顺序‌,记作$C^m_n$。

$\texttt{公式}$

$$C^m_n=\frac{n!}{m!(n-m)!}$$

---

三.经典解题方法

1.相邻问题 → 捆绑法

适用场景‌: 元素必须相邻。

步骤:

① 将相邻元素视为一个整体；

② 整体与其他元素排列；

③ 内部排列。

例子: $A,B$ 必须相邻，$3$人排队： $(A,B)$ 与$C$排列 → $P(2,2) × P(2,2) = 4$ 种

2.‌不相邻问题 → 插空法

适用场景: 元素不能相邻。

步骤:

① 先排其他元素；

② 在空隙中插入不相邻元素。

例‌： $A,B$ 不相邻，$3$人排队:

先排 $C(留 2 空)$，$A,B$插空 → $2! × 2 = 4$ 种

3.分组分配 → 挡板法

适用场景‌：‌相同元素‌ 分给不同组（每组非空）。

$n$个相同元素分$k$组:

$公式$

$$C^{k-1}_{n-1}$$

例子: $10$个糖分$3$人（每人至少$1$个）：$C^2_9$ = 36种

4.正难则反 → 间接法

适用场景‌: 直接求解复杂时，用总数减去无效方案。

例子: 甲不在首位的排列：

总数$5! ,$甲在首位$4! → 120 - 24 = 96$ 种