如何理解错排问题

小灰灰 2023-07-24 09:26 19阅读 0赞

## 一、什么是错排问题 ##

举例：

十本不同的书放在书架，现重新摆放，使得每本书都不在原来的位置上，有几种摆法？  
一个人给十个同学写信，但他把所有的信都装错了信封，问共有多少种错误的方式？  
以上问题推广，就是错排问题。

一个n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的一个排列就称为原排列的一个错排。而研究一个排列的错排个数的问题，就称为错排问题（或称为更列问题）。

## 二、错排公式 ##

n个元素的错排数记为D(n)

D(1)=0; D(2)=1; D(n)=D(n-1)(n-1)+D(n-2)(n-1)

## 三、错排公式的应用 ##

**（1）HDU1465 装错信封事件**

//n封信都装错了信封，且n的范围为[1,20]
    #include<iostream>
    using namespace std;
    int main(){
        
        int n;//[1,20]
        long long a[21]={
        0};
        a[1]=0;a[2]=1;
        for(int i=3;i<21;i++){
        
            a[i]=a[i-1]*(i-1)+a[i-2]*(i-1);//错排公式的应用
        } 
        while(cin>>n){
        
            cout<<a[n]<<endl;
        }
    }

**（2）HDU2048 年会抽奖没人中奖的概率**

//错排公式的应用--n张纸条和n个人刚刚好都不对应，n的范围[1,20]
    //概率：错排的方式总数/n张纸条的可能的排列总数 
    #include<iostream>
    #include<iomanip>
    using namespace std;
    
    __int64 jiechen(int n){
        
        __int64 result=1;
        for(int i=n;i>0;i--){
        
            result=result*i;
        }
        
        return result;
    }
    int main(){
        
        int t;
        cin>>t;
        //错排公式
        __int64 a[21]={
        0,0,1};
        for(int i=3;i<=20;i++){
        
            a[i]=a[i-1]*(i-1)+a[i-2]*(i-1);
        } 
        while(t--){
        
            int n;//人数[1,20]
            cin>>n;
            //计算n!
            __int64 m=jiechen(n);
            //概率 
            double x=(double)a[n]/(double)m;
            
            cout<<setiosflags(ios::fixed);
            cout<<setprecision(2)<<x*100<<"%"<<endl;
        } 
        return 0;
    }

**（3）HDU2049 考新郎问题**

//一共有N对新婚夫妇,其中有M个新郎找错了新娘,发生这种情况一共有多少种可能. 
    //思路：C(N,N-M)*错排M个元素的的D(M) 
    #include<iostream>
    using namespace std;
    
    __int64 f(int n){
        
        __int64 result=1;
        for(int i=n;i>=1;i--){
        
            result=result*i;
        }
        return result;
    } 
    int main(){
        
        int t;
        cin>>t;
        __int64 a[21]={
        0,0,1};
        for(int i=3;i<=20;i++){
          //错排公式
            a[i]=a[i-1]*(i-1)+a[i-2]*(i-1);
        }
        while(t--){
        
            int n,m;
            cin>>n>>m;//n和m的范围[1,20],n对新婚夫妇，m对找错了;
            //C(n,c)的计算
            int c=n-m;
            __int64 b=f(n)/(f(c)*f(n-c));
            
            cout<<b*a[m]<<endl;
        }
        return 0;
    }