「錯排問題」係組合數學 入邊嘅一個問題。考慮一個有 n 個元素嘅排列 ,如果一個排列當中所有嘅元素都唔喺自己原本嘅位置上嘅話,咁呢種排列就叫做原排列嘅一個「錯排」。 n 個元素嘅錯排數記做 !n 。研究一個排列錯排個數嘅問題,就叫做「錯排問題」或者叫「更列問題」。
最早研究錯排問題嘅有尼古拉·伯努利 同歐拉 ,因此歷史上都叫做伯努利-歐拉嘅「裝錯信封問題」。呢個問題有好多具體嘅版本,例如寫信嗰陣將 n 封信裝入 n 個唔同嘅信封裡面,有幾多種全部裝錯信封嘅情況?又例如四個人各自寫一張賀年卡互相送禮,有幾多種送禮嘅方法?自己寫嘅賀年卡唔可以送比自己,所以都係典型嘅錯排問題。
錯排 喺全排列 中嘅機率 係趨於
1
e
{\displaystyle {\frac {1}{e}}}
,所以錯排嘅排法總共有
!
n
=
⌊
n
!
e
⌉
{\displaystyle !n=\left\lfloor {\frac {n!}{e}}\right\rceil }
種。
呢個問題可以用一句說話嚟簡單形容:「n 樣嘢均勻隨機調位,啱啱好 0 個命中自己嘅機率」。
假設 n 足夠大,咁每樣嘢命中返自己嘅機率都趨向
1
n
{\displaystyle {\frac {1}{n}}}
,唔命中自己嘅機率就趨向
1
−
1
n
{\displaystyle 1-{\frac {1}{n}}}
。
所以 n 樣嘢都唔命中自己嘅機率就趨向
(
1
−
1
n
)
n
{\displaystyle \left(1-{\frac {1}{n}}\right)^{n}}
。
而根據 e 嘅定義,可以得出
lim
n
→
∞
(
1
−
1
n
)
n
=
1
e
{\displaystyle \lim _{n\to \infty }\left(1-{\frac {1}{n}}\right)^{n}={\frac {1}{e}}}
。
所以「n 樣嘢均勻隨機調位,啱啱好 0 個命中自己嘅機率」趨向
1
e
{\displaystyle {\frac {1}{e}}}
(只要 n 足夠大)。
咁可以延伸出另一個問題,就係:「n 樣嘢均勻隨機調位,啱啱好 k 個命中自己嘅機率」。
因為除咗命中自己嗰 k 個之外,其他全部都唔可以命中自己,上面已經證明咗,唔命中自己嗰啲嘅機率趨向
1
e
{\displaystyle {\frac {1}{e}}}
。
而命中自己嗰 k 個一定唔可以調位置,因為本來命中,掉咗位置就會變成唔命中,即係乘多咗
k
!
{\displaystyle k!}
,所以要除返佢。
所以「n 樣嘢均勻隨機調位,啱啱好 k 個命中自己嘅機率」趨向
1
k
!
⋅
e
{\displaystyle {\frac {1}{k!\cdot e}}}
。
特別嘅情況係,當 k = n 時:
好明顯只有一種情況會全部命中自己,機率係
1
n
!
{\displaystyle {\frac {1}{n!}}}
。
當 k = n - 1 時:
因為 n - 1 個都命中自己,淨返嗰 1 個一定會命中自己,所以機率係
0
{\displaystyle 0}
。
驗算機率總和係咪等於 1 。假設 n 好大,咁機率總和就係:
∑
k
=
0
∞
1
k
!
⋅
e
{\displaystyle \sum _{k=0}^{\infty }{\frac {1}{k!\cdot e}}}
=
1
e
⋅
∑
k
=
0
∞
1
k
!
{\displaystyle ={\frac {1}{e}}\cdot \sum _{k=0}^{\infty }{\frac {1}{k!}}}
=
1
e
⋅
e
{\displaystyle ={\frac {1}{e}}\cdot e}
=
1
{\displaystyle =1}