插空法排不相邻元素

「不相邻」这个条件正面数很难：它约束的是相邻位置之间的关系，一个一个往位置上填时， 每填一个都要回头看左边是谁。插空法把这件事翻译成一个没有约束的动作：

1. 先排别人：把不受「不相邻」约束的那 $m$ 个元素排成一列，$A_{m}^{m}=m!$ 种。
2. 数空：这 $m$ 个元素之间有 $m-1$ 个空，两端还有 $2$ 个，共 $m+1$ 个空。
3. 往空里插：要插的 $k$ 个元素，一个空最多放一个，即在 $m+1$ 个空里选 $k$ 个并排上顺序， $A_{m+1}^{k}$ 种。
4. 相乘：$m!\cdot A_{m+1}^{k}$。

第 3 步的「一个空最多放一个」就是「不相邻」的全部内容——两个元素挤进同一个空才会挨着， 分在不同空里则中间必然隔着至少一个「别人」。

两条最容易踩的界

（一）先排的那批自己也有约束时，插空并不管。 插空只保证被插的那 $k$ 个两两不相邻；先排好的 $m$ 个之间是什么关系，它一个字都没说。 所以题目若同时要求「甲类不相邻且乙类不相邻」，正确的做法是：先排乙类（不管它相不相邻）， 再按「乙类当前排成了什么样」分类——乙类自己已经挨着的那些排法，必须强制往它们中间的 那个空里插一个甲，剩下的甲才自由。少了这层分类，会把「乙类挨着」的情形整块多算进去。

（二）$k>m+1$ 时答案是 $0$，不是硬算。 空不够用，$A_{m+1}^{k}$ 里 $k>m+1$ 本来就等于 $0$，与「$k$ 个两两不相邻塞不进 $m+1$ 个空」这件事一致。

和捆绑法的分工

• 要相邻 → 捆绑：把要挨着的那几个粘成一个整体先排，再乘内部的排法数；
• 不相邻 → 插空：先排别人，再往空里放。

两者常在同一道题里配合：先用捆绑数出「某类相邻」的种数，再用它做补集。