组合数学——错排问题及其应用

    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>=n
int64 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;
}