错排公式的推导与操纵

猥琐大叔求教pv

来历：知乎



错排题目，又称更列题目，是组合数学中的题目之一。对于它的研讨最早可以追溯到十八世纪，那时他被数学家尼古拉·伯努利和欧拉研讨，是以在历史上也被称为伯努利--欧拉的错装信封题目。这个题目有很多具体的版本，比如在写信时讲n封信装到n个分歧的信封里，有几多种全数装错信封的情况？再比如n小我各写一张贺卡相互赠予，有几多种赠予方式？这些典范的题目都是典型的错排题目。

相信看过上面临于错排题目标简单的先容，大师也都对它有了一些初步的领会，归结起来，就是斟酌一个有n个元素的排列，若一个排列中一切的元素都不在自己本来的位置上，那末这样的排列就称为原排列的一个错排，n个元素的错排数记为D(n)。那末对于这样的排列D(n)有几多种呢？

我们一步一步停止分析：

首先，对于D(n)，有1~n这样n个元素错排，所以对于第一个元素①，它现在能够的位置有(n-1)个，倘使它在第k个元素的位置上，对于第k个元素而言，它地点的位置就有两种能够—第一种，它处在非第一个元素①位置上，所以对于接下来的排列就相当因而n-1个元素的错排，即D(n-1);第二种，它处在第一个元素①的位置上，所以在排列D(n)中有两个元素找到了位置，那末接下来的行列就相当因而n-2个元素的错排。
是以，对于D(n)都有 D_n=(n-1)*(D_{n-1}+D_{n-2}) (n>2)

获得这个递推式以后，我们进一步停止推导：
为了运算的方便，我们设 D_n=n!*N_n ，则有:n!*N_n=(n-1)*(n-2)!*N_{n-2}+(n-1)*(n-1)!*N_{n-1}
双方同时除以(n-1)! ,可得： n*N_n=N_{n-2}+(n-1)*N_{n-1}
移项： N_n-N_{n-1}=(N_{n-2}-N_{n-1})/n = -(1/n)(N_{n-1}-N_{n-2})  
错项相消得： N_n-N_1=1/2!-1/3!+1/4!- ··· ··· +(-1)^{n-1}/(n-1)!+(-1)^n/n!  
由于N(1)=0，N(2)=1, 所以 N_n=1/2!-1/3!+1/4!- ··· ··· +(-1)^{n-1}/(n-1)!+(-1)^n/n!
因而可以获得错排公式为:
D_n=n!*(1/2!-1/3!+1/4!- 1/5!+ ··· ··· +(-1)^{n-1}/(n-1)!+(-1)^n/n!)
这样，我们就经过简单的推导获得了两个关于错排题目标公式！

现在，我们来具体题目具体分析，领会错排公式若何转化为代码来处理考试中现实碰到的题目，我们这里以HDU Online Judge上的一道题考新郎为例，题目是这样的：


阅读题目后我们不难发现，这道题的本质就是求解排列组合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<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long _cuopai[50];
long long jiecheng[22]={1,1,2,6,24,120,720,5040,40320,
                        362880,3628800,39916800,479001600,
                                                6227020800,87178291200,1307674368000,
                                                20922789888000,355687428096000,6402373705728000,
                                                121645100408832000,2432902008176640000};

long long cuopai(int x)
{
        if(_cuopai[x]) return _cuopai[x];
        if(x==1) return 0;
        if(x==2) return 1;
    return _cuopai[x]=(x-1)*(cuopai(x-1)+cuopai(x-2));
}

long long c(int y,int z)
{
        return jiecheng[y]/(jiecheng[z]*jiecheng[y-z]);
}

int main()
{
        memset(_cuopai,0,sizeof(_cuopai));
        int a;
        cin>>a;
        for(int i=1;i<=a;++i)
        {
                int m,n;
            cin>>m>>n;
            cout<<c(m,n)*cuopai(n)<<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)^{m-1}/(m-1)!+(-1)^m/m!)/(n-m)!
#include<iostream>
#include<cstdio>
using namespace std;
int m,n;
long long jiecheng[22]={1,1,2,6,24,120,720,5040,40320,
                        362880,3628800,39916800,479001600,
                                                6227020800,87178291200,1307674368000,
                                                20922789888000,355687428096000,6402373705728000,
                                                121645100408832000,2432902008176640000};

long long cuopai_()
{
        long long sum=0,a=jiecheng[n],b=jiecheng[n-m];
        for(int i=2;i<=m;++i)
        {
                a/=i;
                if(i%2==0)
                  sum+=a;
                else
                  sum-=a;
                //cout<<"sum["<<i<<"]"<<sum<<endl;
        }
        return sum/b;
}

int main()
{
        int x;
        cin>>x;
        for(int i=1;i<=x;++i)
        {
                cin>>n>>m;
                cout<<cuopai_()<<endl;
        }
        return 0;
}



原文地址：https://zhuanlan.zhihu.com/p/42610134
免责声明：
1、文章部分图片源于收集，均为表示图；
2、一切文章、图片、音频视频文件等材料版权归版权一切人一切；
3、因非原创文章及图片等内容没法和版权者联系，如原作者或编辑以为作品不宜上网供阅读，或不应无偿利用，请实时告诉我们，以敏捷采纳适当办法，避免给双方形成不需要的经济损失；
4、本页面内容由爬虫法式自动收集于互联网，如无意中加害了媒体或小我的常识产权，请电邮【E-Mail:cb@yoyodoc.com】告之，我们将于24小时内删除。

把心掏給珎丶

你好，叨教这个能用c编码出来吗？

聪明牛得

讲的太好

小玛哥1

求问大神……为什么可以为了运算方便设Dn为n！*Nn，小白太菜了看不懂这里555

无热天龙中

由于他看答案了

forregistuse

k放到除1外的位置上，怎样就是d(n-1)种错排了？终极还有一个x会放到1的位置上，那末究竟是哪n-1个数错排？

yao不回忆

实在按照递推公式，一路往下递推到D2便可以了

ADDJ2017

k放到1之外的位置的情况，相当于在剩下的n-1个数中，k原本在1的位置，而重排不能放到1的位置，只能放在其他n-2个位置上，所以这类情况是等价于n-1个数的错排的。

春意盎然2016

N（2）=1/2