错排公式的推导与应用

更新于: | 阅读次数: | 评论数:
字数统计: 1.2k | 阅读时长 ≈ 5

问题简介

错排问题，又称更列问题，是组合数学中的问题之一。对于它的研究最早可以追溯到十八世纪，当时他被数学家尼古拉·伯努利和欧拉研究，因此在历史上也被称为伯努利—欧拉的错装信封问题。这个问题有许多具体的版本，比如在写信时讲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!*N_n$,

则有: $n!N_n=(n-1)(n-2)!N_{n-2}+(n-1)(n-1)!*N_{n-1}$

两边同时除以(n-1)! ,可得：

移项：

错项相消得：

由于N(1)=0，N(2)=1, 所以 $N_n=1/2!-1/3!+1/4!- ··· ··· +(-1)^{n-1}/(n-1)!+(-1)^n/n!$

于是可以得到错排公式为:

这样，我们就通过简单的推导得到了两个关于错排问题的公式！

例题分析

现在，我们来具体问题具体分析，了解错排公式如何转化为代码来解决考试中实际遇到的问题，我们这里以HDU Online Judge上的一道题考新郎为例，题目是这样的：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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-通项公式:

这里可以根据题目做一下变形: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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;
}
-------------本文结束感谢您的阅读-------------