组合数学-错排问题

问题一：

写信时将n封信装到n个不同的信封里，有多少种全部装错信封的情况？

问题二：

四人各写一张贺年卡互相赠送，有多少种赠送方法？自己写的贺年卡不能送给自己。

问题三：

五对儿情侣吸了毒很high，打赌玩点儿刺激的，每个男生可以带一个女孩子回家过夜，但是不能带自己的女朋友，有几种组合可能？

这些问题都可以称之为错排问题,错排问题是组合数学中的问题之一。考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为Dn。

最早研究错排问题的是尼古拉·伯努利和欧拉，因此历史上也称为伯努利-欧拉的装错信封的问题。

枚举法解决问题：

对于情况较少的排列，可以使用枚举法。

+ 当n=1时，全排列只有一种，不是错排，D1 = 0。
+ 当n=2时，全排列有两种，即1、2和2、1，后者是错排，D2 = 1。
+ 当n=3时，全排列有六种，即1、2、3；1、3、2；2、1、3；2、3、1；3、1、2；3、2、1，其中只有有3、1、2和2、3、1是错排，D3=2。用同样的方法可以知道D4=9。
+ 最小的几个错排数是：D1 = 0，D2 = 1，D3=2，D4 = 9，D5 = 44，D6 = 265，D7 = 1854.

递推法解决问题：

对于排列数较多的情况，难以采用枚举法。这时可以用递归思想推导错排数的递推公式。
显然D1=0，D2=1。当n≥3时，不妨设n排在了第k位，其中k≠n，也就是1≤k≤n-1。那么我们现在考虑第n位的情况。

+ 当k排在第n位时，除了n和k以外还有n-2个数，其错排数为Dn-2。
+ 当k不排在第n位时，那么将第n位重新考虑成一个新的“第k位”，这时的包括k在内的剩下n-1个数的每一种错排，都等价于只有n-1个数时的错排（只是其中的第k位会换成第n位）。其错排数为Dn-1。

所以当n排在第k位时共有Dn-2+Dn-1种错排方法，又k有从1到n-1共n-1种取法，我们可以得到：

Dn=(n-1)(Dn-1+Dn-2)

非数学角度来考虑问题，有这个递归公式，我们就可以写程序算任意n的错排数了。

参考

更多相关请移步维基百科，恩，我只是维基百科的搬运工。