更 新 至 版 本 1.0.0\huge \text{\orange 更 \red 新 \pink 至 \blue 版 \purple 本 1.0.0}更 新 至 版 本 1.0.0
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
排列组合讲解
你是否一碰到排列组合题目就无从下手？
你是否分不清什么时候用加法、什么时候用乘法？
你是否总是混淆排列与组合，列式频频出错？
你是否搞不懂捆绑、插空、隔板各类解题方法的适用场景？
带着这些常见困惑，让我们循序渐进，学习排列组合！
前置知识
> 阶乘
n!=1×2×3×⋯×nn!=1\times2\times3\times\cdots\times nn!=1×2×3×⋯×n
0!=10!=10!=1
> 排列
公式：
Anm=n!(n−m)!A_n^m=\frac{n!}{(n-m)!}Anm =(n−m)!n!
或者：
Anm=n(n−1)(n−2)⋯(n−m+1)A_n^m=n(n-1)(n-2)\cdots(n-m+1)Anm =n(n−1)(n−2)⋯(n−m+1)
性质：
Ank=k⋅CnkA_n^k = k\cdot C_n^kAnk =k⋅Cnk
Ank=n⋅An−1k−1A_n^k = n\cdot A_{n-1}^{k-1}Ank =n⋅An−1k−1
Ank=(n−k+1)⋅Ank−1A_n^k = (n - k + 1)\cdot A_n^{k-1}Ank =(n−k+1)⋅Ank−1
An+1k=Ank+k⋅Ank−1A_{n+1}^k = A_n^k + k\cdot A_n^{k-1}An+1k =Ank +k⋅Ank−1
Ann=n!=n×(n−1)!A_n^n = n! = n \times (n-1)!Ann =n!=n×(n−1)!
> 组合
公式：
Cnk=n!k!×(n−k)!C_n^k=\frac{n!}{k! \times (n - k)!}Cnk =k!×(n−k)!n!
或者
Cnk=n(n−1)⋯(n−k+2)(n−k+1)k×(k−1)⋯2×1C_n^k = \frac{n(n-1)\cdots(n-k+2)(n-k+1)}{k\times(k-1)\cdots2 \times 1}Cnk =k×(k−1)⋯2×1n(n−1)⋯(n−k+2)(n−k+1)
性质：
Cn0=Cnn=1C_n^0=C_n^n=1Cn0 =Cnn =1
Cnk=Cnn−kC_n^k=C_n^{n-k}Cnk =Cnn−k
Cn+1k=Cnk+Cnk−1C_{n+1}^k=C_n^k+C_n^{k-1}Cn+1k =Cnk +Cnk−1
> 加法原理
做一件事有多类互不重叠方案，各类方案数相加。
逻辑：分类，任选一类就能做完这件事。
举个例子：
从甲地去乙地，火车 333 班，大巴 222 班，总出行方式为：3+2=5（种）3+2=5（种）3+2=5（种）
> 乘法原理
做一件事分先后几步，每步缺一不可，步步相乘。
逻辑：分步，每一步都要完成才成事。
举个例子：
从甲地去乙地，先要去丙地，有 333 班车，再要从丙地去乙地，有 222 班车，总出行方式为：3×2=6（种）3 \times 2=6（种）3×2=6（种）
经典例题及解答方法
> 题型一：特殊元素优先法
题目： 7 人排队，甲不能站排头、乙不能站排尾，共有多少种排队方式？
解题思路： 先算出七人全排列总数，再减去甲在排头的情况、乙在排尾的情况，最后加回重复减去的“甲在排头且乙在排尾”的情况。（这是一道有点集合思路的问题）
答案公式： A77−2A66+A55=7!−2×6!+5!=3720A_7^7 - 2A_6^6 + A_5^5 = 7! - 2\times 6! + 5! = 3720A77 −2A66 +A55 =7!−2×6!+5!=3720
通用解题方法： 先计算全排列 - 特殊情况 + 特殊情况有两个交集 - 特殊情况有三个交集 + 特殊情况有四个交集...
> 题型二：捆绑法
题目： 7 人排队，A、B、C 三人必须紧挨在一起，求总排列数。
解题思路： 将 A、B、C 整体捆绑视为一个新元素，一共 7−3+1=47-3+1=47−3+1=4 个元素全排列，再乘以 A、B、C 内部的排列顺序。
答案公式： A44×A33=24×6=144A_4^4 \times A_3^3 = 24 \times 6 = 144A44 ×A33 =24×6=144
通用解题方法： 先把捆绑内容视为一个元素，先计算全排列，再乘以捆绑内容的内部排列个数
> 题型三：插空法
题目： 7 人排队，甲、乙不能相邻，求排列总数。
解题思路： 先无条件排列其余 5 人，5 人排好产生 6 个空位，从中选 2 个空位排入甲、乙，保证两人不相邻。
答案公式： A55⋅A62=120×30=3600A_5^5 \cdot A_6^2 = 120 \times 30 = 3600A55 ⋅A62 =120×30=3600
通用解题方法： 先全排列其他人，再计算产生空位个数=其他人的个数+1，然后乘以将插空元素插入产生空位的个数时的排列个数
> 题型四：定序问题
题目： 7 人排队，A、B、C 三人顺序固定（A 在前、B 中间、C 在后），求排法数。
解题思路： 整体全排列后除以固定元素的全排列数，剔除多余顺序。
答案公式： A77A33=7!3!=840\dfrac{A_7^7}{A_3^3} = \dfrac{7!}{3!} = 840A33 A77 =3!7! =840
通用解题方法： 先计算排列个数，再除以多余的顺序
> 题型五：环形排列问题
题目： 6 个人围着圆桌吃饭，求总坐法数。
解题思路： 环形排列无固定起点，旋转算同一种
答案公式： (6−1)!=5!=120(6-1)! = 5! = 120(6−1)!=5!=120
通用解题方法： 直接公式 (n−1)!(n-1)!(n−1)!
> 题型六：隔板法
题目： 10 个完全相同的糖果分给 3 名小朋友，每人至少 1 颗，求分法数。
解题思路： 10 颗糖果产生 9 个空隙，插入 2 块隔板分成三份。
答案公式： C92=36C_9^2 = 36C92 =36
通用解题方法： 直接公式 C要分配的数量−1给的人数−1C_{\text{要分配的数量} - 1}^{\text{给的人数} - 1}C要分配的数量−1给的人数−1
> 题型七：间接法
题目： 从 8 男 5 女中选出 4 人，至少 1 名女生，求选法总数。
解题思路： 总选法减去“没有女生、全是男生”的极端情况。
答案公式： C134−C84=715−70=645C_{13}^4 - C_8^4 = 715 - 70 = 645C134 −C84 =715−70=645
通用解题方法： 总选法减去极端情况的数量
> 题型八：错排问题（错位重排问题）
题目： 4 个人各拿一把钥匙，全部交换后没人拿到自己钥匙，一共有几种拿法？
解题思路： 使用错位排列通项公式，代入 DnD_nDn 和 n=4n=4n=4 计算。
答案公式： D4=4!(1−11!+12!−13!+14!)=9D_4 = 4!\left(1-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\dfrac{1}{4!}\right) = 9D4 =4!(1−1!1 +2!1 −3!1 +4!1 )=9
通用解题方法：
记公式：
Dn=n!(1−11!+12!−13!+⋯+(−1)n1n!)D_n = n!\left(1-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\cdots+(-1)^n \dfrac{1}{n!}\right)Dn =n!(1−1!1 +2!1 −3!1 +⋯+(−1)nn!1 )
递推公式：
Dn=(n−1)(Dn−1+Dn−2)D_n = (n-1)(D_{n-1}+D_{n-2})Dn =(n−1)(Dn−1 +Dn−2 )
初始值：D1=0, D2=1D_1 = 0,\ D_2 = 1D1 =0, D2 =1
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
由于本人排列组合学的不太好，才写的这篇文章用于整理及复习
觉得有做的不好的直接喷！
本篇文章纯手搓，无AI！
@AC君 求加精！
有要补充的，请及时评论！
