錯排

「錯排問題」係組合數學入邊嘅一個問題。考慮一個有 n 個元素嘅排列，如果一個排列當中所有嘅元素都唔喺自己原本嘅位置上嘅話，咁呢種排列就叫做原排列嘅一個「錯排」。 n 個元素嘅錯排數記做 !n 。研究一個排列錯排個數嘅問題，就叫做「錯排問題」或者叫「更列問題」。 最早研究錯排問題嘅有尼古拉·伯努利同歐拉，因此歷史上都叫做伯努利-歐拉嘅「裝錯信封問題」。呢個問題有好多具體嘅版本，例如寫信嗰陣將 n 封信裝入 n 個唔同嘅信封裡面，有幾多種全部裝錯信封嘅情況？又例如四個人各自寫一張賀年卡互相送禮，有幾多種送禮嘅方法？自己寫嘅賀年卡唔可以送比自己，所以都係典型嘅錯排問題。

計法

錯排喺全排列中嘅機率係趨於 ${\frac {1}{e}}$，所以錯排嘅排法總共有 $!n=\left\lfloor {\frac {n!}{e}}\right\rceil$ 種。

簡單證明

呢個問題可以用一句說話嚟簡單形容：「n 樣嘢均勻隨機調位，啱啱好 0 個命中自己嘅機率」。

假設 n 足夠大，咁每樣嘢命中返自己嘅機率都趨向 ${\frac {1}{n}}$ ，唔命中自己嘅機率就趨向 $1-{\frac {1}{n}}$ 。

所以 n 樣嘢都唔命中自己嘅機率就趨向 $\left(1-{\frac {1}{n}}\right)^{n}$ 。

而根據 e 嘅定義，可以得出 $\lim _{n\to \infty }\left(1-{\frac {1}{n}}\right)^{n}={\frac {1}{e}}$ 。

所以「n 樣嘢均勻隨機調位，啱啱好 0 個命中自己嘅機率」趨向 ${\frac {1}{e}}$ (只要 n 足夠大)。

延伸問題

咁可以延伸出另一個問題，就係：「n 樣嘢均勻隨機調位，啱啱好 k 個命中自己嘅機率」。

因為除咗命中自己嗰 k 個之外，其他全部都唔可以命中自己，上面已經證明咗，唔命中自己嗰啲嘅機率趨向 ${\frac {1}{e}}$ 。

而命中自己嗰 k 個一定唔可以調位置，因為本來命中，掉咗位置就會變成唔命中，即係乘多咗 $k!$ ，所以要除返佢。

所以「n 樣嘢均勻隨機調位，啱啱好 k 個命中自己嘅機率」趨向 ${\frac {1}{k!\cdot e}}$ 。

特別嘅情況係，當 k = n 時：

好明顯只有一種情況會全部命中自己，機率係 ${\frac {1}{n!}}$ 。

當 k = n - 1 時：

因為 n - 1 個都命中自己，淨返嗰 1 個一定會命中自己，所以機率係 $0$ 。

驗算機率總和係咪等於 1 。假設 n 好大，咁機率總和就係：

$\sum _{k=0}^{\infty }{\frac {1}{k!\cdot e}}$

$={\frac {1}{e}}\cdot \sum _{k=0}^{\infty }{\frac {1}{k!}}$

$={\frac {1}{e}}\cdot e$

$=1$

睇埋

• 全排列
• 弱排列
• 排列組合