$\huge \text{\orange 更 \red 新 \pink 至 \blue 版 \purple 本 1.0.0}$

---

排列组合讲解

你是否一碰到排列组合题目就无从下手？
你是否分不清什么时候用加法、什么时候用乘法？
你是否总是混淆排列与组合，列式频频出错？
你是否搞不懂捆绑、插空、隔板各类解题方法的适用场景？
带着这些常见困惑，让我们循序渐进，学习排列组合！

前置知识

阶乘

$n!=1\times2\times3\times\cdots\times n$
$0!=1$

排列

公式：
$A_n^m=\frac{n!}{(n-m)!}$
或者：
$A_n^m=n(n-1)(n-2)\cdots(n-m+1)$

性质：
$A_n^k = k\cdot C_n^k$

$A_n^k = n\cdot A_{n-1}^{k-1}$

$A_n^k = (n - k + 1)\cdot A_n^{k-1}$

$A_{n+1}^k = A_n^k + k\cdot A_n^{k-1}$

$A_n^n = n! = n \times (n-1)!$

组合

公式：
$C_n^k=\frac{n!}{k! \times (n - k)!}$
或者
$C_n^k = \frac{n(n-1)\cdots(n-k+2)(n-k+1)}{k\times(k-1)\cdots2 \times 1}$

性质：
$C_n^0=C_n^n=1$

$C_n^k=C_n^{n-k}$

$C_{n+1}^k=C_n^k+C_n^{k-1}$

加法原理

做一件事有多类互不重叠方案，各类方案数相加。
逻辑：分类，任选一类就能做完这件事。
举个例子：
从甲地去乙地，火车 $3$ 班，大巴 $2$ 班，总出行方式为：$3+2=5（种）$

乘法原理

做一件事分先后几步，每步缺一不可，步步相乘。
逻辑：分步，每一步都要完成才成事。
举个例子：
从甲地去乙地，先要去丙地，有 $3$ 班车，再要从丙地去乙地，有 $2$ 班车，总出行方式为：$3 \times 2=6（种）$

经典例题及解答方法

题型一：特殊元素优先法

题目： 7 人排队，甲不能站排头、乙不能站排尾，共有多少种排队方式？
解题思路： 先算出七人全排列总数，再减去甲在排头的情况、乙在排尾的情况，最后加回重复减去的“甲在排头且乙在排尾”的情况。（这是一道有点集合思路的问题）
答案公式： $A_7^7 - 2A_6^6 + A_5^5 = 7! - 2\times 6! + 5! = 3720$
通用解题方法： 先计算全排列 - 特殊情况 + 特殊情况有两个交集 - 特殊情况有三个交集 + 特殊情况有四个交集...

题型二：捆绑法

题目： 7 人排队，A、B、C 三人必须紧挨在一起，求总排列数。
解题思路： 将 A、B、C 整体捆绑视为一个新元素，一共 $7-3+1=4$ 个元素全排列，再乘以 A、B、C 内部的排列顺序。
答案公式： $A_4^4 \times A_3^3 = 24 \times 6 = 144$
通用解题方法： 先把捆绑内容视为一个元素，先计算全排列，再乘以捆绑内容的内部排列个数

题型三：插空法

题目： 7 人排队，甲、乙不能相邻，求排列总数。
解题思路： 先无条件排列其余 5 人，5 人排好产生 6 个空位，从中选 2 个空位排入甲、乙，保证两人不相邻。
答案公式： $A_5^5 \cdot A_6^2 = 120 \times 30 = 3600$
通用解题方法： 先全排列其他人，再计算产生空位个数=其他人的个数+1，然后乘以将插空元素插入产生空位的个数时的排列个数

题型四：定序问题

题目： 7 人排队，A、B、C 三人顺序固定（A 在前、B 中间、C 在后），求排法数。
解题思路： 整体全排列后除以固定元素的全排列数，剔除多余顺序。
答案公式： $\dfrac{A_7^7}{A_3^3} = \dfrac{7!}{3!} = 840$
通用解题方法： 先计算排列个数，再除以多余的顺序

题型五：环形排列问题

题目： 6 个人围着圆桌吃饭，求总坐法数。
解题思路： 环形排列无固定起点，旋转算同一种
答案公式： $(6-1)! = 5! = 120$
通用解题方法： 直接公式 $(n-1)!$

题型六：隔板法

题目： 10 个完全相同的糖果分给 3 名小朋友，每人至少 1 颗，求分法数。
解题思路： 10 颗糖果产生 9 个空隙，插入 2 块隔板分成三份。
答案公式： $C_9^2 = 36$
通用解题方法： 直接公式 $C_{\text{要分配的数量} - 1}^{\text{给的人数} - 1}$

题型七：间接法

题目： 从 8 男 5 女中选出 4 人，至少 1 名女生，求选法总数。
解题思路： 总选法减去“没有女生、全是男生”的极端情况。
答案公式： $C_{13}^4 - C_8^4 = 715 - 70 = 645$
通用解题方法： 总选法减去极端情况的数量

题型八：错排问题（错位重排问题）

题目： 4 个人各拿一把钥匙，全部交换后没人拿到自己钥匙，一共有几种拿法？
解题思路： 使用错位排列通项公式，代入 $D_n$ 和 $n=4$ 计算。
答案公式： $D_4 = 4!\left(1-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\dfrac{1}{4!}\right) = 9$
通用解题方法：
记公式：
$D_n = n!\left(1-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\cdots+(-1)^n \dfrac{1}{n!}\right)$
递推公式：
$D_n = (n-1)(D_{n-1}+D_{n-2})$
初始值：$D_1 = 0,\ D_2 = 1$

---

由于本人排列组合学的不太好，才写的这篇文章用于整理及复习
觉得有做的不好的直接喷！
本篇文章纯手搓，无AI！
@AC君 求加精！
有要补充的，请及时评论！