有人問了我關於錯排的問題。

據說這個問題是由伯努利裝信封的時候想到的，就是現在寫了

n

封信準備給

n

個不同的人，如果不看是給誰的信封直接裝信，問剛好

n

封信全部裝錯的情況數有多少種？

容斥原理

這個其實也是置換沒有不動點的問題，最常見的一種做法（其實是我知道的做法）是用

容斥原理

。眾所周知：

\begin{align*} \left\vert \bigcup_{k=1}^n A_k\right\vert&=\sum_{k\leq n}\vert A_k\vert-\sum_{i<j\leq n}\vert A_i\cap A_j\vert+\sum_{i<j<k\leq n}\vert A_i\cap A_j\cap A_k\vert+\ldots\\ &+(-1)^{n-1}\vert A_1\cap A_2\cap\ldots\cap A_n\vert \end{align*}

於是可以記第

i

封信恰好放到第

i

個信封的事件為

A_i

，則所有不合法的情況數為：

\begin{align*} \left\vert \bigcup_{k=1}^n A_k\right\vert&=\sum_{k\leq n}\vert A_k\vert-\sum_{i<j\leq n}\vert A_i\cap A_j\vert+\sum_{i<j<k\leq n}\vert A_i\cap A_j\cap A_k\vert+\ldots\\ &+(-1)^{n-1}\vert A_1\cap A_2\cap\ldots\cap A_n\vert \end{align*}

再由每封信裝錯事件地位相等，上式又可化為

C_n^1\vert A_1\vert-C_n^2\vert A_1\cap A_2\vert+C_n^3\vert A_1\cap A_2\cap A_3\vert+\ldots+(-1)^n C_n^n\vert A_1\cap A_2\cap A_3\ldots\cap A_n\vert \\

因此，所有的情況就應該等於

\begin{align*} &n!-\left\vert \bigcup_{k=1}^n A_k\right\vert\\ =&n!-C_n^1\vert A_1\vert+C_n^2\vert A_1\cap A_2\vert-C_n^3\vert A_1\cap A_2\cap A_3\vert+\ldots+(-1)^nC^n_n\vert A_1\cap A_2\cap A_3\cap\ldots\cap A_n\vert\\ =&C_n^0n!-C_n^1(n-1)!+C_n^2(n-2)!-C_n^3(n-3)!+\ldots+(-1)^nC_n^n0! \end{align*} \\

由於

C_n^i

剛好在

楊輝三角

第

n+1

行，故可以用楊輝三角進行記憶。但是我比較喜歡由

C_n^i(n-i)!=\frac{n!}{i!} \\

得到最後總情況數為

n!\left(\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}+\ldots+(-1)^n\frac{1}{n!}\right) \\

這個就有點妙不可言了，而且如果

n\to \infty

，則括號裡面就是

e^x

的麥克勞林展開式在

x=-1

時的無窮級數。或者說令上式等於

a_n

，則

\lim_{n\to\infty}\frac{n!}{a_n}={e} \\

遞推

當然除了容斥原理還有別的方法，記

n

封信錯排的情況數為

a_n

，我們利用遞推來求解通項公式。

由於現在的

n

封信需要錯排，於是第一封信可以裝到除第一個信封的任意位置，不妨裝到第二個信封。那麼現在有兩種情況：

第一種：第二封信裝到第一個信封，那麼問題變為

(n-2)

封信的錯排問題，即

a_{n-2}

；

第二種：第二封信一定不能裝到第一封去，那麼現在就是第

i

封不能裝到第

i

個

(i>2)

，而第二封不能裝到第

1

個信封，所以就是

(n-1)

封信的錯排問題，即

a_{n-1}

。

於是有遞推公式：

a_n=(n-1)(a_{n-1}+a_{n-2}) \\

兩邊同除以

n!

\begin{align*} &\frac{a_n}{n!}=\frac{n-1}{n}\frac{a_{n-1}}{(n-1)!}+\frac{1}{n}\frac{a_{n-2}}{(n-2)!}\\ \Leftrightarrow&\frac{a_n}{n!}-\frac{a_{n-1}}{(n-1)!}=-\frac{1}{n}\left(\frac{a_{n-1}}{(n-1)!}-\frac{a_{n-2}}{(n-2)!}\right)\\ \Rightarrow&\frac{a_n}{n!}-\frac{a_{n-1}}{(n-1)!}=(-1)^{n-1}\frac{1}{n}\times\frac{1}{n-1}\times\ldots\times\frac{1}{2}(\frac{a_1}{1!}-\frac{a_0}{0!})=(-1)^n \frac{1}{n!} \end{align*} \\

進一步累加即得

\begin{align*} &\frac{a_n}{n!}-\frac{a_0}{0!}=-\frac{1}{1!}+\frac{1}{2!}-\ldots+(-1)^n\frac{1}{n!}\\ \Rightarrow&a_n=n!\left(\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\ldots+(-1)^n\frac{1}{n!}\right) \end{align*} \\

結語

這個問題應該還有更多有意思的事情，但是還沒能好好去思考。