所谓错排便是每一个数的都不会出现在原先排列的位置，如原排列1234中便不会出现1342这种错排，因为1的位置还是在原排列的位置之中。有公式
错排.png
其中有D1=0，D2=1 。
公式推导如下：
1.在n个数中将其中一个数k放到除它位置外的可能有（n-1）个可能。（设它放在位置m上）
2.那么m位置上的数便有两种情况，有可能在前一个数的位置上和不可能在前一个数的位置上，而对于第一种的可能结果有（n-1）种，后面有（n-2）种可能。
那不难得到错排的可能性如上公式所述。
而组合数，便是能够从n个数中挑出其中的m个数（n>m），第一个数有n个位置选择，第二个数有（n-1）个位置选择，直到m个数有（n-m+1）个位置选择。那么可能结果便为（n-m+1）到n的乘积。然而这个却是有序的排列，若要做到无序排列，还得在所选m个数中在进行一次排列组合，即m！的可能性。可得知无序排列为
n！/【m！（n-m）！】
我们可以从oj-2068来掌握这两种方法。
题目链接：RPG的错排
2068.png
题目要求找出一半以上即为成功，即奇数在整形除2时要多出1。有n个女生，那么找出k个女生即可的可能答案，将k直到n的可能组合一一算出，在中间的每种可能中又有一个对应的错排，那么2者得到的乘积之和在加上1便是最后的答案。因在错排计算中，若全部选中的，错排为0，但又有全部选中这一可能性，故而要还上这一可能性。
第一个便是组合数的计算，但就算使用了long的整形，在21！之上便开始溢出，那么便要对公式 n！/【m！（n-m）！】进行变换，即为[（n-m+1）...n]/（n-m）！。
第二个便是将错排的结果求出，这个并没有多大问题。
import java.util.*;
public class Main{
public static void main (String[] args) {
long[] d = new long [26];
d[1]=0; d[2]=1;
int i;
for(i=3;i<26;i++) {
d[i]=(i-1)*(d[i-1]+d[i-2]);
} //错排的计算
Scanner scan = new Scanner(System.in);
while(scan.hasNextInt()) {
int n=scan.nextInt();
if(n==0)break;
int k;
long sum=0;
k=n/2;
if(n%2==1) k++; //奇数的一半以上
for(i=k;i<=n;i++) {
sum = sum+d[n-i]*jie(i,n);
}
System.out.println(sum+1);
}
}
//组合数的计算
public static long jie(int i,int n) {
long k=0,sum2=1,sum3=1;
if(n==i) k = 1;
else {
for(k=i+1;k<=n;k++) {
sum2 *= k;
}
for(k=1;k<=n-i;k++) {
sum3 *= k;
}
k=sum2/sum3;}
return k;
}
}
