距离高考已经快2个月了，本蒟蒻在这次高考中被吊锤……
今天，@飒羽 提到的一道题让我想到了无比有意思的错排问题:
一、定义
一共有n类元素，每种元素有1个。考虑这n个元素的排列，若一个排列中所有元素都不在原排列同类元素的位置上，那么就称为原排列的普通错排。
二、错排问题的求解:
例: 有一名邮递员需要去投递n封信, n封信的编号分别为1, 2, 3, ..., n, n个邮箱的编号也分别为1, 2, 3, ..., n, 记A_n为n封信均不投入对应编号的邮箱的事件数. （我们称第i封信对应编号的邮箱为第i个邮箱）, 求A_n .
解: 首先注意到A_1=0, A_2=1.
考虑一般情形：第n个邮箱一定被投入了第i封信, 其中i\in\left\{1,2,...,n-1\right\}.
考虑第i个邮箱.
(1) 若第i个邮箱被投入了第n封信, 相当于n元素和i元素发生了一个置换. 此时事件数为 (n-1)A_{n-2} .
(2) 若第i个邮箱中不是第n封信, 我们考虑剩下n-1个邮箱和n-1封信, 其余各邮箱和各封信可以看作一个错排问题, 而第i个邮箱中不是第n封信, 事实上相当于剩下n-1个邮箱和n-1封信之间发生错排. 此时事件数为 (n-1)A_{n-1}.
从而A_n=(n-1)(A_{n-2}+A_{n-1})(n\ge3)
下面来求解它的通项公式.
A_n-nA_{n-1}=-(A_{n-1}-(n-1)A_{n-2})
而A_2-(2)A_1=1, 故
A_n-nA_{n-1}=(-1)^n
两边同除n!, 得
\dfrac{A_n}{n!}-\dfrac{A_{n-1}}{(n-1)!}=\dfrac{(-1)^n}{n!}
累加可知: n\ge2时，有
\dfrac{A_n}{n!}=\sum\limits_{k = 2}^n {\frac{{{{\left( { - 1} \right)}^k}}}{{k!}}}+A_1
而A_1=0=\dfrac{(-1)^0}{0!}+\dfrac{(-1)^1}{1!}, 故
\dfrac{A_n}{n!}=\sum\limits_{k = 0}^n {\frac{{{{\left( { - 1} \right)}^k}}}{{k!}}}(n\in\mathrm{N}^*)
左端的\dfrac{A_n}{n!}即为错排的概率.
由熟知的Tailor公式我们可知:
{{\rm{e}}^x} = \sum\limits_{k = 0}^{ + \infty } {\frac{{{x^k}}}{{k!}}}
故当x\to+\infty时，P_n \to \rm{e}^{-1} .
