所謂錯排便是每一個數(shù)的都不會出現(xiàn)在原先排列的位置，如原排列1234中便不會出現(xiàn)1342這種錯排悼院，因為1的位置還是在原排列的位置之中。有公式
錯排.png
其中有D1=0咒循，D2=1 据途。
公式推導(dǎo)如下：
1.在n個數(shù)中將其中一個數(shù)k放到除它位置外的可能有（n-1）個可能。（設(shè)它放在位置m上）
2.那么m位置上的數(shù)便有兩種情況叙甸，有可能在前一個數(shù)的位置上和不可能在前一個數(shù)的位置上颖医，而對于第一種的可能結(jié)果有（n-1）種，后面有（n-2）種可能裆蒸。
那不難得到錯排的可能性如上公式所述熔萧。
而組合數(shù)，便是能夠從n個數(shù)中挑出其中的m個數(shù)（n>m），第一個數(shù)有n個位置選擇佛致，第二個數(shù)有（n-1）個位置選擇贮缕，直到m個數(shù)有（n-m+1）個位置選擇。那么可能結(jié)果便為（n-m+1）到n的乘積俺榆。然而這個卻是有序的排列感昼，若要做到無序排列，還得在所選m個數(shù)中在進(jìn)行一次排列組合肋演，即m抑诸！的可能性〉猓可得知無序排列為
n蜕乡！/【m！（n-m）梗夸！】
我們可以從oj-2068來掌握這兩種方法层玲。
題目鏈接：RPG的錯排
2068.png
題目要求找出一半以上即為成功，即奇數(shù)在整形除2時要多出1反症。有n個女生辛块，那么找出k個女生即可的可能答案，將k直到n的可能組合一一算出铅碍，在中間的每種可能中又有一個對應(yīng)的錯排润绵，那么2者得到的乘積之和在加上1便是最后的答案。因在錯排計算中胞谈，若全部選中的尘盼，錯排為0，但又有全部選中這一可能性烦绳，故而要還上這一可能性卿捎。
第一個便是組合數(shù)的計算，但就算使用了long的整形径密，在21午阵！之上便開始溢出，那么便要對公式 n享扔！/【m底桂！（n-m）！】進(jìn)行變換惧眠，即為[（n-m+1）...n]/（n-m）籽懦！。
第二個便是將錯排的結(jié)果求出锉试，這個并沒有多大問題猫十。
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++; //奇數(shù)的一半以上
for(i=k;i<=n;i++) {
sum = sum+d[n-i]*jie(i,n);
}
System.out.println(sum+1);
}
}
//組合數(shù)的計算
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;
}
}
