错排问题--错排公式的推导及应用

持续创作，加速成长！这是我参与「掘金日新计划 · 10 月更文挑战」的第22天，点击查看活动详情

错排问题

错排问题是组合数学中的问题之一。考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为Dn。 研究一个排列错排个数的问题，叫做错排问题或称为排列问题。

最早研究错排问题的是尼古拉·伯努利和欧拉，因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本，如在写信时将n封信装到n个不同的信封里，有多少种全部装错信封的情况？又比如四人各写一张贺年卡互相赠送，有多少种赠送方法？自己写的贺年卡不能送给自己，所以也是典型的错排问题。

例如有

n

封写好了的信，收件人不同，胡乱放入

n

个写了地址的信封中，寄出，求没有一个收件人收到他所应接收的信的概率。当

n=4

，在4! = 24个排列之中，只有9个是错排：

BADC, BCDA, BDAC,

CADB, CDAB, CDBA,

DABC, DCAB, DCBA,

所以有关概率为9/24 = 37.5%

推导

显然D1=0，D2=1。当n≥3时，不妨设n排在了第k位，其中k≠n，也就是1≤k≤n-1。那么我们现在考虑第n位的情况。

• 当k排在第n位时，除了n和k以外还有n-2个数，其错排数为Dn-2。
• 当k不排在第n位时，那么将第n位重新考虑成一个新的“第k位”，这时的包括k在内的剩下n-1个数的每一种错排，都等价于只有n-1个数时的错排（只是其中的第k位会换成第n位）。其错排数为Dn-1。

所以当n排在第k位时共有Dn-2+Dn-1种错排方法，又k有从1到n-1共n-1种取法，我们可以得到：

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

在上面我们得到Dn=(n-1)(Dn-1+Dn-2) 从这个公式中我们可以推出Dn的通项公式，方法如下：

为书写方便，记Dn = n!Mn，则M1 = 0, M2 = {\displaystyle {\frac {1}{2}}}

{\frac {1}{2}}

当n大于等于3时，由Dn = (n-1)(Dn-1 + Dn-2)，即

n!M_{n}=(n-1)(n-1)!M_{​{n-1}}+(n-1)(n-2)!M_{​{n-2}}=n!M_{​{n-1}}-(n-1)!M_{​{n-1}}+(n-1)!M_{​{n-2}}

。 所以，

nM_{n}-nM_{​{n-1}}=-M_{​{n-1}}+M_{​{n-2}}

。

于是有

M_{n}-M_{​{n-1}}=-{\frac {1}{n}}(M_{​{n-1}}-M_{​{n-2}})=...=(-{\frac {1}{n}})(-{\frac {1}{n-1}})...(-{\frac {1}{3}})(M_{2}-M_{1})=(-1)^{n}{\frac {1}{n!}}.

所以

{\begin{aligned}M_{​{n}}-M_{​{n-1}}&=(-1)^{​{n}}{\frac {1}{n!}}\M_{​{n-1}}-M_{​{n-2}}&=(-1)^{​{(n-1)}}{\frac {1}{(n-1)!}}\\vdots \quad &=\quad \vdots \M_{2}-M_{1}&=(-1)^{2}{\frac {1}{2!}}\\end{aligned}}

将上面式子分边累加，得

M_{n}=(-1)^{2}{\frac {1}{2!}}+(-1)^{3}{\frac {1}{3!}}...+(-1)^{​{n}}{\frac {1}{n!}}.

因此，我们得到错排公式

D_{n}=n!M_{n}=n!({\frac {1}{2!}}-{\frac {1}{3!}}+...+(-1)^{n}{\frac {1}{n!}}).

简化公式

错位排列数的公式可以简化为：

D_{n}=\left\lfloor {\frac {n!}{e}}+0.5\right\rfloor ,

其中的

\lfloor n\rfloor

为高斯取整函数（小于等于 n 的最大整数）。

这个简化公式可以由之前的错排公式推导出来。事实上，考虑指数函数在 0 处的泰勒展开：

{\begin{aligned}e^{​{-1}}&=1+{\frac {\left(-1\right)^{1}}{1!}}+{\frac {\left(-1\right)^{2}}{2!}}+\cdots +\left(-1\right)^{n}{\frac {1}{n!}}+{\frac {e^{​{-c}}}{(n+1)!}}\left(c-1\right)^{n}\&={\frac {1}{2!}}-{\frac {1}{3!}}+\cdots +\left(-1\right)^{n}{\frac {1}{n!}}+R_{n}\&={\frac {D_{n}}{n!}}+R_{n}\\end{aligned}}

所以，

{\frac {n!}{e}}-D_{n}=n!,R_{n}

。其中 Rn 是泰勒展开的余项，c 是介于 0 和 1 之间的某个实数。Rn 的绝对值上限为

|R_{n}|\leqslant {\frac {e^{0}}{(n+1)!}}={\frac {1}{(n+1)!}}

{\Big |}{\frac {n!}{e}}-D_{n}{\Big |}\leqslant {\frac {n!}{(n+1)!}}={\frac {1}{(n+1)}}

当 n≥2 时，

{\frac {1}{(n+1)}}

严格小于 0.5，所以

D_{n}=n!\left({\frac {1}{2!}}-{\frac {1}{3!}}+...+(-1)^{n}{\frac {1}{n!}}\right)

是最接近

{\frac {n!}{e}}

的整数，可以写成

D_{n}=\left\lfloor {\frac {n!}{e}}+0.5\right\rfloor .

错位排列数的公式可以简化为：

D_{n}=\left\lfloor {\frac {n!}{e}}+0.5\right\rfloor ,

其中的

\lfloor n\rfloor

为高斯取整函数（小于等于 n 的最大整数）。

这个简化公式可以由之前的错排公式推导出来。事实上，考虑指数函数在 0 处的泰勒展开：

{\begin{aligned}e^{​{-1}}&=1+{\frac {\left(-1\right)^{1}}{1!}}+{\frac {\left(-1\right)^{2}}{2!}}+\cdots +\left(-1\right)^{n}{\frac {1}{n!}}+{\frac {e^{​{-c}}}{(n+1)!}}\left(c-1\right)^{n}\&={\frac {1}{2!}}-{\frac {1}{3!}}+\cdots +\left(-1\right)^{n}{\frac {1}{n!}}+R_{n}\&={\frac {D_{n}}{n!}}+R_{n}\\end{aligned}}

所以，

{\frac {n!}{e}}-D_{n}=n!,R_{n}

。其中 Rn 是泰勒展开的余项，c 是介于 0 和 1 之间的某个实数。Rn 的绝对值上限为

|R_{n}|\leqslant {\frac {e^{0}}{(n+1)!}}={\frac {1}{(n+1)!}}

{\Big |}{\frac {n!}{e}}-D_{n}{\Big |}\leqslant {\frac {n!}{(n+1)!}}={\frac {1}{(n+1)}}

当 n≥2 时，

{\frac {1}{(n+1)}}

严格小于 0.5，所以

D_{n}=n!\left({\frac {1}{2!}}-{\frac {1}{3!}}+...+(-1)^{n}{\frac {1}{n!}}\right)

是最接近

{\frac {n!}{e}}

的整数，可以写成

D_{n}=\left\lfloor {\frac {n!}{e}}+0.5\right\rfloor .

递推公式：Dn=(n-1)(Dn-1+Dn-2) n>3, D1 = 0 , D2 = 1;也就是上述中推导错排公式所用到的公式

应用

下面用错排递推公式做几个几个例子；

例1；装错信封的问题（经典原型）HDU1465题

写n封信，全部装错信封，求有多少种全部装错的方式

#include<iostream>
using namespace std; 
int main() {
    int n;	
    long long d[21] = {0,0,1};//将d[0],d[1],d[2]初始化	
    for(int i=3;i<=20;i++) {		
        d[i] = (i-1)*(d[i-1]+d[i-2]);	
    } 	
    while(cin >> n) {		
        cout << d[n] <<endl;	
    }	
    return 0;
}

例2：考新郎HUD2049

首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.

阅读题目后我们不难发现，这道题的本质就是求解排列组合C(n,m)与错排m个元素D(m)的乘积，因此这道题的代码也十分简单，以下提供两种AC程序：

//#方法1：递推公式--D(n)=(n-1)*(D(n-1)+D(n-2)) [D(1)=0，D(2)=1]
#include<bits/stdc++.h>//万能头文件，只有少部分oj支持
using namespace std; 
int main() {	
    int ti,n,m;	
    long long f[21] = {0,0,1},t[21] = {1,1,2};
    for(int i=3;i<=20;i++) {		
        f[i] = (i-1)*(f[i-1]+f[i-2]);		
        t[i] = t[i-1]*i;	
    }	
    cin >> ti;	
    while(ti--) {		
        cin >> n >> m;		
        long long a = t[n]/t[m]/t[n-m];		
        cout << a*f[m] <<endl;	
    }	
    return 0;
}

/*
#方法2：通项公式--D(n)=n!*(1/2!-1/3!+1/4!- 1/5!+ ··· ··· +((-1)^(n-1))/(n-1)!+((-1)^n)/n! )
这里可以根据题目做一下变形:F(n,m)=C(n,m)*D(m)=n!*(1/2!-1/3!+1/4!- 1/5!+ ··· ··· +((-1)^(n-1))/(n-1)!+((-1)^n)/n! )/(n-m)!
*/
#include<bits/stdc++.h>
using namespace std; 
int ti,n,m;
long long f[21] = {0,0,1},t[21] = {1,1,2}; 
long long sol() {	
    long long sum=0,a=t[n],b=t[n-m];	
    for(int i=2; i<=m; ++i) {	
        a/=i;		
    if(i%2==0)		
        sum+=a;		
    else			
        sum-=a;	
    }	
    return sum/b;
} 
int main() {	
    for(int i=3; i<=20; i++) {	
        f[i] = (i-1)*(f[i-1]+f[i-2]);		
        t[i] = t[i-1]*i;	
    }	
    cin >> ti;	
    while(ti--) {	
        cin >> n >> m;		
        cout << sol() <<endl;	
    }	
    return 0;
}