组合数学——错排问题及其应用
??? n个有序的元素应有n!个不同的排列，若一个排列使得所有的元素都不在原来位置上，则称这个排列为错排。
错排公式推导
??? 设n个数1,2,3...,n错排数目为Dn，对于其中任意一个数i：
??? (1) 数i分别与其他的n-1个数交换位置，其余n-2个数进行错排，共得到(n-1)Dn-2个错排；
??? (2) 对除数i以外的n-1个数进行错排，然后i与其中每个数互换，得到(n-1)Dn-1个错排。
??? 因此，得到递推关系：Dn=(n-1)(Dn-1 + Dn-2),D1=0,D2=1。它的通解为Dn=n!-C(n,1)(n-1)!+C(n,2)(n-2)! - ... +(-)C(n,n)1!。
?
HDU2048
题意：给出n个元素，求错排的概率。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;typedef __int64 int64;const int N = 21;int64 d[N];int64 f[N];int main(){ int i; int c,n; d[1] = 0; d[2] = 1; f[1] = 1; f[2] = 2; for(i = 3; i < N; i++) { d[i] = (i-1)*(d[i-1] + d[i-2]); f[i] = f[i-1]*i; } scanf("%d",&c); while(c--) { scanf("%d",&n); double p = 1.0*d[n]/f[n]*100.0; printf("%.2lf%%\n",p); } return 0;}?
?
?
HDU2068
题意：给出n个元素，求有>=一半的元素在自己的位置的组合数。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;typedef __int64 int64;const int N = 15;int64 d[N];//c(m,n),m>=nint64 composite(int64 m, int64 n){ int64 i,j; if(n==0) return 1; int64 result = 1; for(i=m,j=1; j <= n; i--,j++) result = result*i/j; return result;}int main(){ int i; d[1] = 0; d[2] = 1; for(i = 3; i < N; i++) d[i] = (i-1)*(d[i-1]+d[i-2]); int n; while(true) { scanf("%d",&n); if(n==0) break; int k = n/2; int64 result = 0; for(i = 2; i <= k; i++) result += composite(n,i)*d[i]; printf("%I64d\n",result+1); } return 0;}?
?
?
?