22.02 排列组合 16 种核心解题模型与策略

🟦 排列组合 16 种核心解题模型与策略

核心心法

“结构定模型，限制定顺序”。排列组合问题的复杂性源于各种限制条件（相邻、不相邻、定序、重复等）。掌握这 16 种核心模型，本质上是掌握了将复杂计数问题“降维”为基础加乘原理的工具箱。

---

1. 特殊元素和特殊位置优先安排

• 核心思想：优先处理有特殊限制的元素（如“首位不为0”）或位置（如“末位为奇数”），消除矛盾。
• 例：0,1,2,3,4,5 组成无重复五位奇数。
  • 步1：末位 $C_3^1$；步2：首位 $C_4^1$（不为0且不为末位）；步3：余位 $A_4^3$。
  • 结论：$C_3^1\times C_4^1\times A_4^3=288$。

---

2. 相邻元素捆绑法

• 核心思想：相邻元素看作一个整体（大元素），排完后再考虑内部排列。
• 例：7人站一排，甲乙相邻且丙丁相邻。
  • 步1：整体排 $A_5^5$；步2：内部自排 $A_2^2\times A_2^2$。
  • 结论：$A_5^5\times A_2^2\times A_2^2=480$。

---

3. 不相邻问题插空法

• 核心思想：先排无限制元素，再将不相邻元素插入形成的空隙中。
• 例：4个舞蹈、2个相声、3个独唱，舞蹈不连续。
  • 步1：排余项 $A_5^5$；步2：插空位 $A_6^4$（5个元素形成6个空）。
  • 结论：$A_5^5\times A_6^4$。

---

4. 定序问题整除法

• 核心思想：先全排列，再除以定序元素的全排列数以消除顺序影响。
• 例：7人排队，甲乙丙3人顺序一定。
  • 结论：$\frac{A_7^7}{A_3^3}$。

---

5. 重排问题求幂法

• 核心思想：允许重复抽取，每一步的选择数均相等。
• 例：6名实习生分配到7个车间。
  • 结论：$7^6$。

---

6. 圆排列问题

• 核心思想：圆排列无首尾，需固定一个元素。
• 结论：$n$ 个不同元素圆排列种数为 $(n-1)!$。

---

7. 多排问题直排法

• 核心思想：将多排位置拉直成一排来处理。
• 例：8人前后两排各4人，甲乙前排，丙后排。
  • 结论：$A_4^2\times A_4^1\times A_5^5$。

---

8. 排列组合混合问题先选后排

• 核心思想：先从总体中选出符合要求的元素组，再对这组元素进行排列。
• 例：5个球装入4个盒，每盒至少一个。
  • 步1：选2球绑在一起 $C_5^2$；步2：4个元素排入4盒 $A_4^4$。
  • 结论：$C_5^2\times A_4^4$。

---

9. 小集团问题先整体后局部

• 核心思想：类似于捆绑法，但侧重于集团内外的多层次排列。
• 例：1-5组成五位数，恰有两个偶数夹在1,5之间。
  • 结论：$A_2^2\times A_2^2\times A_2^2$（整体排 $\times$ 1,5自排 $\times$ 偶数自排）。

---

10. 元素相同问题隔板法 (Star and Bars)

• 核心思想：在相同元素的空隙中插入“挡板”进行分配。
• 例：10个名额分给7个班，每班至少一个。
  • 结论：$C_9^6$。
• 模型扩展：
  • 正整数解：$x_1+\cdots +x_n=m⟹C_{m-1}^{n-1}$。
  • 非负整数解：$x_1+\cdots +x_n=m⟹C_{m+n-1}^{n-1}$。

---

11. 正难则反总体淘汰法

• 核心思想：当正面分类过多时，用总数减去违规数。
• 结论：$N_{\text{total}}-N_{\text{illegal}}$。

---

12. 不同元素分组分配法

• 核心思想：先分组（注意均匀分组需除以 $A_k^k$），再分配。
• 均匀分组判定：若有 $k$ 组元素个数相等，需除以 $A_k^k$。

---

13. 合理分类与分步

• 核心思想：寻找“全能型”关键元素作为分类标准。

---

14. 错位排列 (Derangement)

• 核心思想：每个元素都不在对应位置。
• 常用数：$a_1=0,a_2=1,a_3=2,a_4=9,a_5=44$。

---

15. 分解与合成策略

• 例：30030 的偶因数个数。
  • 核心：必须含质因数 2，其余 5 个质因数任取。
  • 结论：$2^5-1$（即 $C_5^1+\cdots +C_5^5$）。

---

16. 特殊模型

1. 异面直线对：$3(C_n^4-m)$。
2. 圆内交点：$C_n^4$。
3. 连续号码：$C_{n-2(m-1)}^2$。
4. 传球递推：$a_n=4^{n-1}-a_{n-1}$。

---

⚠️ 考场避坑与做题技巧

隔板法的使用前提

隔板法只能用于相同元素（如名额、一样的球）分给不同对象（如班级、盒子）。如果球是不同的，必须使用分组分配法。

重复计数的重灾区

在“平均分组”问题中，如 4 人平均分成两组，如果不除以 $A_2^2$，就会将 $\{A,B\}$ 与 $\{C,D\}$ 的组合计算两次。

“至少”不一定都要用间接法

当“至少”的情况只有 1-2 类时，直接分类计算往往比总数减去反面更不容易出错。