二重错排
Published:
二重错排
1. 问题定义
一重错排问题中，我们要求一个排列 $\pi$ 满足：
\[\pi(i) \neq i \quad \forall i\]在此基础上 二重错排 要求：
对所有 $i = 1,2,\dots,n-1$：
\[\pi(i) \neq i,\quad \pi(i) \neq i+1\]对 $i = n$（循环边界）：
\[\pi(n) \neq n,\quad \pi(n) \neq 1\]
2. 正确位置的等价建模
先考虑如下问题：
- 在一个 $n-1$ 阶的台阶，如下图
- 括号中第一个数表示序列索引，第二个数表示排入的数字
- 要求：每行每列均只能选择1个点
等价于：
将阶梯拉成一个环，在一个长度为 $2n$ 的环上，选择 $k$ 个点，要求不相邻。
3. 组合构造得出等价模型的计算式
首先定义：
\[f(m,k) := \#\left\{ \text{在长度为 } m \text{ 的圆环上选取 } k \text{ 个两两不相邻的点的方案} \right\}\]下面用两种组合方式计算同一个量，从而得出 $f(m,k)$：
方法一：先选点，再切断
- 在环上选 $k$ 个不相邻点：共有 $f(m,k)$ 种
- 剩下 $m-k$ 个点，从这些未选点中任选一个作为“切断点”，将环变成链
因此：
\[N= f(m,k)\cdot (m-k)\]方法二：先切断，再选点
- 在环上任选一点，将环切断成链（有 $m$ 种切法）
- 在有 $m-1$ 个点的链上选 $k$ 个不相邻点
使用插空法，结果为：
\[\binom{m-k}{k}\]因此：
\[N = m \cdot \binom{m-k}{k}\]两种方法等价：
\[f(m,k)(m-k) = m \binom{m-k}{k}\]得到：
\[\boxed{ f(m,k) = \frac{m}{m-k} \binom{m-k}{k} }\]4. 回到二重错排问题
使用容斥原理计算满足的排列数量：
设 $\pi \in S_n$ 是 ${1,2,\dots,n}$ 上的一个排列。
定义：
\[P_i = \{\pi \in S_n \mid \pi(i)=i \ \text{or} \ i+1\}, \quad i=1,2,\dots,n,\]其中
\[n+1 \equiv 1\]容斥原理展开：
\[\begin{aligned} N(\bar{P_1}\bar{P_2} \cdots \bar{P_n}) &= N - \sum_{i} N(P_i) + \sum_{i<j} N(P_i P_j) \cdots + (-1)^n\, N(P_1 P_2\cdots P_n) \end{aligned}\]其中：
\[N = n!\] \[\#\{\text{满足 } P_{i_1},\dots,P_{i_k}\} = f(2n,k)\]由上文可知：
\[f(2n,k)=\frac{2n}{2n-k}\binom{2n-k}{k}\]一旦选定了正确排列 $k$ 个位置：
- 固定 这 $k$ 个位置，剩余 $n-k$ 个位置自由排列，即：
因此：
\[N(P_1 P_2\cdots P_k) = \frac{2n}{2n-k}\binom{2n-k}{k}(n-k)!\]代入容斥原理公式：
\[\begin{aligned} N(\bar{P_1}\bar{P_2} \cdots \bar{P_n}) &= \sum_{k=0}^n (-1)^k \cdot f(2n,k) \cdot (n-k)! \\ &= \sum_{k=0}^n (-1)^k \cdot \frac{2n}{2n-k} \binom{2n-k}{k} (n-k)! \end{aligned}\]从而得到二重错排的排列数为：
\[\boxed{ N(\bar{P_1}\bar{P_2} \cdots \bar{P_n}) = \sum_{k=0}^n (-1)^k \frac{2n}{2n-k} \binom{2n-k}{k} (n-k)! }\]5. 应用：卢卡斯夫妻入座问题
下面是渲染后的PDF：