錯位排列

定義

錯位排列（derangement）是沒有任何元素出現在其有序位置的排列。即，對於 \(1\sim n\) 的排列 \(P\)，如果滿足 \(P_i\neq i\)，則稱 \(P\) 是 \(n\) 的錯位排列。

例如，三元錯位排列有 \(\{2,3,1\}\) 和 \(\{3,1,2\}\)。四元錯位排列有 \(\{2,1,4,3\}\)、\(\{2,3,4,1\}\)、\(\{2,4,1,3\}\)、\(\{3,1,4,2\}\)、\(\{3,4,1,2\}\)、\(\{3,4,2,1\}\)、\(\{4,1,2,3\}\)、\(\{4,3,1,2\}\) 和 \(\{4,3,2,1\}\)。錯位排列是沒有不動點的排列，即沒有長度為 1 的循環。

容斥原理的計算

全集 \(U\) 即為 \(1\sim n\) 的排列，\(|U|=n!\)；屬性就是 \(P_i\neq i\). 套用補集的公式，問題變成求 \(\left|\bigcup_{i=1}^n\overline{S_i}\right|\).

可以知道，\(\overline{S_i}\) 的含義是滿足 \(P_i=i\) 的排列的數量。用容斥原理把問題式子展開，需要對若干個特定的集合的交集求大小，即：

\[ \left|\bigcap_{i=1}^{k}S_{a_i}\right| \]

其中省略了 \(a_i<a_{i+1}\) 的條件以方便表示。上述 \(k\) 個集合的交集表示有 \(k\) 個變量滿足 \(P_{a_i}=a_i\) 的排列數，而剩下 \(n-k\) 個數的位置任意，因此排列數：

\[ \left|\bigcap_{i=1}^{k}S_{a_i}\right|=(n-k)! \]

那麼選擇 \(k\) 個元素的方案數為 \(\dbinom{n}{k}\)，因此有：

\[ \begin{aligned} \left|\bigcup_{i=1}^n\overline{S_i}\right| &=\sum_{k=1}^n(-1)^{k-1}\sum_{a_{1,\cdots,k} }\left|\bigcap_{i=1}^{k}S_{a_i}\right|\\ &=\sum_{k=1}^n(-1)^{k-1}\dbinom{n}{k}(n-k)!\\ &=\sum_{k=1}^n(-1)^{k-1}\frac{n!}{k!}\\ &=n!\sum_{k=1}^n\frac{(-1)^{k-1} }{k!} \end{aligned} \]

因此 \(n\) 的錯位排列數為：

\[ D_n=n!-n!\sum_{k=1}^n\frac{(-1)^{k-1} }{k!}=n!\sum_{k=0}^n\frac{(-1)^k}{k!} \]

錯位排列數列的前幾項為 \(0,1,2,9,44,265\)（OEIS A000166）。

遞推的計算

把錯位排列問題具體化，考慮這樣一個問題：

\(n\) 封不同的信，編號分別是 \(1,2,3,4,5\)，現在要把這五封信放在編號 \(1,2,3,4,5\) 的信封中，要求信封的編號與信的編號不一樣。問有多少種不同的放置方法？

假設考慮到第 \(n\) 個信封，初始時暫時把第 \(n\) 封信放在第 \(n\) 個信封中，然後考慮兩種情況的遞推：

前面 \(n-1\) 個信封全部裝錯；
前面 \(n-1\) 個信封有一個沒有裝錯其餘全部裝錯。

對於第一種情況，前面 \(n-1\) 個信封全部裝錯：因為前面 \(n-1\) 個已經全部裝錯了，所以第 \(n\) 封只需要與前面任一一個位置交換即可，總共有 \(D_{n-1}\times (n-1)\) 種情況。

對於第二種情況，前面 \(n-1\) 個信封有一個沒有裝錯其餘全部裝錯：考慮這種情況的目的在於，若 \(n-1\) 個信封中如果有一個沒裝錯，那麼把那個沒裝錯的與 \(n\) 交換，即可得到一個全錯位排列情況。

其他情況，不可能通過一次操作來把它變成一個長度為 \(n\) 的錯排。

於是可得，錯位排列數滿足遞推關係：

\[ D_n=(n-1)(D_{n-1}+D_{n-2}) \]

這裏也給出另一個遞推關係：

\[ D_n=nD_{n-1}+{(-1)}^n \]

其他關係

錯位排列數有一個向下取整的簡單表達式，增長速度與階乘僅相差常數：

\[ D_n=\left\lfloor\frac{n!}{\mathrm{e}}\right\rfloor \]

隨着元素數量的增加，形成錯位排列的概率 P 接近：

\[ P=\lim_{n\to\infty}\frac{D_n}{n!}=\frac{1}{\mathrm{e}} \]

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用