错排公式 详细解答

错排问题
错排问题 就是一种递推式，不过它比较著名且常用，所以要熟记！

错排问题：有n个正整数1，2，3，……n，将这n个正整数重新排列，使其中的每一个数都不在原来的位置上，这种排列称为正整数1，2，3，……n的错排，问这n个正整数的排个数是多少？
设这n个正整数的错排个数为an，为了探求an的表达式，我们先从最特殊的情形入手。
当n=1时，由于只有一个数1，不可能有错排，所以a1=0.
当n=2时，两个数的错排是唯一的，所以a2=1.
当n=3时，三个数1、2、3只有2、3、1和3、1、2两种错排，所以a3=2.
当n=4时，四个数1、2、3、4的错排有：2、1、4、3；2、3、4、1；2、4、1、3；3、1、4、2；3、4、2、1；4、1、2、3；4、3、1、2；4、3、2、1，共有9种错排，所以a4=9.
上面使用的是枚举法，当n较大时，这种方法是很麻烦的、难以解决问题的，必须另辟蹊径，现在考虑用排除法求出1、2、3、4这四个正整数的错排的种数，从中摸索出规律。
对于四个正整数1、2、3、4，这四个数的全排列数为4！。
有一个数不错排的情况应排除，由于1排在第1位的有3！种，2排在第2位的有3！种，……4排在第4位的有3！种，所以共应排除4×3！种。
然而在排除有一个数不错排的情况时，把同时有两个数不错排的情况也排除了，应予以补上，由于1、2分别排在第1、第2位上的情况共有2！种，同理1、3分别排在第1、第3位上的情况也有2！种，……，这四个数中同时有两个数不错排的情况共有种，所以应补上 种。在补上同时有两个数不错排的情况时，把同时有三个数不错排的情况也补上了，应予以排除，四个数中有1、2、3不错排，1、2、4不错排，1、3、4不错排和2、3、4不错排共 种情况，所以应排除 种。
在排除同时有三个数不错排的情况时，把同时有四个数不错排的情况也排除了，所以应补上同时有四个数不错排的情况仅1、2、3、4这一种。

对于第二个公式：
递归关系式为：f(n)=(n-1)(f(n-1)+f(n-2))
解释：
n 个不同元素的一个错排可由下述两个步骤完成：
第一步，“错排” 1 号元素（将 1 号元素排在第 2 至第 n 个位置之一），有 n - 1 种方法。
第二步，“错排”其余 n - 1 个元素，按如下顺序进行。视第一步的结果，若1号元素落在第 k 个位置，第二步就先把 k 号元素“错排”好， k 号元素的不同排法将导致两类不同的情况发生：
1、 k 号元素排在第1个位置，留下的 n - 2 个元素在与它们的编号集相等的位置集上“错排”，有 f(n -2) 种方法；
2、 k 号元素不排第 1 个位置，这时可将第 1 个位置“看成”第 k 个位置(也就是说本来准备放到k位置为元素，可以放到1位置中),于是形成（包括 k 号元素在内的） n - 1 个元素的“错排”，有 f(n - 1) 种方法。据加法原理，完成第二步共有 f(n - 2)+f(n - 1) 种方法。
根据乘法原理， n 个不同元素的错排种数
f(n) = (n-1)[f(n-2)+f(n-1)] (n>2) 。

HDU-2049-考新郎
http://acm.hdu.edu.cn/showproblem.php?pid=2049
这个题目就需要用到错排。