第16章　相邻、不相邻与环形排列

1. 相邻捆绑

两个对象必须相邻，把它们看成一个整体排列，再乘内部排列数。$k$ 个对象必须相邻，则整体作为一个“块”，块内还可有 $k!$ 种内部顺序。

若同类对象各自不同、类别必须连在一起，先排列类别块，再乘每类内部排列。例如三类各有 $a,b,c$ 幅不同作品，方式数为 $3!a!b!c!$，若限制某一类不能在两端则再扣除不合法类别顺序。

2. 插空不相邻

先排不受限制的对象，形成空位，再把不能相邻对象放入不同空位。$n$ 个不同对象排成一列，另有 $k$ 个不同对象且它们彼此不相邻：

$$n!(\genfrac{}{}{0ex}{}{n+1}{k})k!.$$

若两类对象不能彼此相邻，则“先排 A 再插 B”只保证 B 彼此不邻，需要额外检查 B 与 A 的限制。例如先排 C、D、E 有 $3!=6$ 种，形成 4 个空位；再从空位中选 2 个放 A、B，有 $C_4^2\times 2!=12$ 种，所以 A、B 不相邻的排法共 $6\times 12=72$ 种。

3. 环形排列

圆桌上 $n$ 个不同人，旋转视为相同，则共有 $(n-1)!$ 种；镜像通常仍视为不同，除非题目明确不区分方向。围成一圈时固定一个对象消除旋转对称。

环形相邻问题可先固定一个人，再按线性排列处理其余位置；“两位大人不相邻”常用总数减去两大人相邻数。