错排问题
什么是错排问题
若有n个人，都想给其他n-1个人中的任意一个送信（当然不能送给自己），请问一共有多少种送法？
建模
对于一个具体的题目，数学上喜欢抽象，于是可以把这样的问题抽象为一个数学模型，下面给出定义
对于n个元素，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就叫原排列的一个错排，n个元素的错排数记为D(n)。研究一个排列的错排个数的问题，就叫做错排问题或称为更列问题
归纳
下面给出一些较小的错排数：
对于只包含1个元素的序列，全排列为1！=1，即没有错排，则错排数D(1)=0，
对于2个元素的序列，全排列为2！=2，假设是1，2；则错排数只有一组：2，1。则错排数D(2)=1;
以此类推
0，1，2，9，44，265，14833…….
总结
上述推导就是使用枚举法将错排数一一找出，聪明的犊子应该已经发现了其中的规律，下面给出一个递归的推导式：
$ D(n)=(n-1)*(D(n-1)+D(n-2)) $
感兴趣的同学可以使用数学归纳法证明一下这个推导式的正确性，这里不予讨论。
推导
观察发现，此递推式是一个递归方法（指有限步骤内，根据特定的法则或公式对一个或多个前面的元素进行运算，以确定一系列元素的方法）。于是思考，能否使用递归的思想来推导这个递归方法。
对于n个元素，显然D(1)=0,D(2)=1,则思考当$ n \geq 3 $时的情况
若此时第n个数，恰好放在k的位置，且$ k！=n $，则对于n的位置上，就出现了两种情况：
Ⅰ.n的位置上恰好为k时
Ⅱ.n的位置上不为k时
下面对两种情况分类讨论：
Ⅰ.此时情况较为简单，即n和k调换位置，其他个数恰好构成了新的错排问题，错排数为D(n-2)。
Ⅱ.此时因为k在n的位置上的情况已经讨论过了，所以在此情况下，无法在n的位置上，此时可以将n的位置视为元素k原本的位置（仔细思考）。那么k与剩下个数又构成了新的错排问题，错排数为D(n-1)；
综上，在n确认放在k的位置（$ k!=n D(n-1)+D(n-2) n-1 D(n)=(n-1)\times (D(n-1)+D(n-2)) $
递归证明
因为错排数中存在某种规律，于是我们尝试推导错排数所组成的数列的通项公式。
通过之前的推导我们知道，
$ D(n)=(n-1) \times (D(n-1)+D(n-2)) $
此处为了方便起见，我们设 $ D(n)=n! \times M(n) $(为什么之后用其他的方法证明),其中
$ M(1)=0,M(2)=1/2……M(n)=1/n $
于是原推导式变为了：
$ D(n)=n! \times M(n)=(n-1)\times ((n-1)! \times M(n-1)+(n-2)! \times M(n-2)) $
展开得:
$ n! \times M(n)=(n-1) \times (n-1)! \times M(n-1)+(n-1) \times (n-2)! \times M(n-2) $
化简得:
$ n! \times M(n)=n! \times M(n-1)-(n-1)! \times M(n-1)+(n-1)! \times M(n-2) $
同除(n-1)!:
$ n \times M(n)=n \times M(n-1)-M(n-1)+M(n-2) $
移项得:
$ M(n)-M(n-1)=(-1/n) \times (M(n-1)-M(n-2)) $
于是展开
$ (M(n-1)-M(n-2)) $
得:
$ M(n)-M(n-1)=(-1/n) \times (-1/(n-1)) \times (M(n-2)-M(n-3))) $
依次类推得：
$ M(n)-M(n-1)=(-1/n) \times (-1/(n-1))……(-1/3) \times (M(2)-M(1)) \times (-1) \times (-1) $(多乘两个-1为了方便合并)
化简得:
$ M(n)-M(n-1)=(-1)^n \times 1/n! $
于是使用累加法：
$ M(n)-M(n-1)=(-1)^n \times 1/n! $
$ M(n-1)-M(n-2)=(-1)^{n-1} \times 1/(n-1)! $
$ M(n-2)-M(n-3)=(-1)^{n-2} \times 1/(n-2)! $
……
$ M(2)-M(1)=(-1)^2 \times 1/2! $
累加得:
$ M(n)-M(1)=(-1)^2 \times 1/2!+…+(-1)^{n-2} \times 1/(n-2)!+(-1)^{n-1} \times 1/(n-1)!+(-1)^n \times 1/n! $
则 $ D(n)=n! \times (1/2!-1/3!+1/4!-…+(-1)^n \times 1/n!) $
容斥原理证明
于是我们得到了错排数的通项公式，聪明的犊子可能已经发现了，在使用递归法证明的时候里面蕴藏了一点容斥原理的知识，下面我们使用容斥原理来证明这个通项公式
对于n个元素，如果k的位置刚好放的是k，那么这样的排列一共有(n-1)!个，考虑到k可以取n个不同的值，所以一共有 $ n_(n-1)! $ 种情况，至少放对了一个，但是我们需要求的是一个都没放对的排列个数，所以我们需要使用总的排列数减去这些，即 $ n!-n_(n-1)! $ ,但是至少放对了一个的情况下又包含了放对2个的情况，我们多减了一次，于是我们需要加回来，但是至少放对2个的情况种又包含了至少放对3个的情况，于是又要加上,……,依次类推，我们得到式子：
$ D(n)=n!-C_n^1\times (n-1)! + C^2_n \times (n-2)! - C^3_n \times (n-3)!+…+(-1)^n \times C^n_n \times 0! $
即 $ D(n)=n!(1-1/1!+1/2!+…+(-1)^n\times 1/n!) $
即 $ D(n)=n!(1/2!+…+(-1)^n\times 1/n!) $
