同時釋出在我的個人部落格:https://hushhw.cn/posts/learn/15287.html
以下是原文:
之前就遇到過錯排公式的題,但是自己沒有注意這個知識點,以為隻要硬記住就好啦,結果就是不知道推導過程完全記不住呀,是以今天認真整理一下錯排公式相關的點。
錯排公式的推導
考慮一個有n個元素的排列,若一個排列中所有的元素都不在自己原來的位置上,那麼這樣的排列就稱為原排列的一個錯排,n個元素的錯排記為D(n)。下面就是求出D(n)為多少中排列。
首先我們拿第一個元素的放置來了解一下這個過程:把元素1放在除自己原來的位置以外的位置,共有(n-1)種,假設第一個元素被放在了第k個元素的位置上,對第k個元素而言就有兩種情況要讨論了,第一種,它放在非第一個位置上,是以對于接下來的排列就相當于是n-1個元素的錯排,即D(n-1);第二種,它就放在第1個元素的位置上,是以排列D(n)中有兩個元素已經找到位置了,那麼接下來就隻需要考慮n-2個元素的錯排,即D(n-2)。由此,我們就可以寫出遞推式對于D(n)都有D(n)=(n-1)*(D(n-1)+D(n-2))【特殊的情況 D(1)=0, D(2)=1】。
下面通過這個遞推關系進行推導:
為了運算友善,我們設D(n)=n!N(n),則有:
n!N(n) = (n-1)(n-2)!N(n-2) + (n-1)(n-1)!N(n-1); 對兩邊同時除以(n-1)!,可得:
nN(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-1) - N(n-2) = -(1/(n-1))(N(n-2) - N(n-3))
……
N(2) - N(1) = 1/2;
由此,将每個式子相加得到:N(n) - N(1) = (1/2! - 1/3! + 1/4! - ……+((-1)^(n-1))/(n-1)! + (-1)^n/n!)
由于N(1) = 0,是以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)^(n-1))/(n-1)! + (-1)^n/n!)。
錯排公式的應用解題
【hdu2049】考新郎
題目描述
在一場盛大的集體婚禮中,為了使婚禮進行的豐富一些,司儀臨時想出了有一個有意思的節目,叫做"考新郎",具體的操作是這樣的:輸入
輸入資料的第一行是一個整數C,表示測試執行個體的個數,然後是C行資料,每行包含兩個整數N和M(1< M<=N<=20)輸出
對于每個測試執行個體,請輸出一共有多少種發生這種情況的可能,每個執行個體的輸出占一行。示例輸入
2
2 2
3 2
最開始做着題的時候就直接求解排列組合C(n,m),沒有考慮錯排m個元素D(m)的問題,這裡用上面的兩種方法分别寫出代碼:
方法一:遞推公式 D(n)=(n-1)*(D(n-1)+D(n-2)) [D(1)=0,D(2)=1]
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
long long f[22];
void init()//錯排
{
f[1]=0;
f[2]=1;
for(int i=3;i<=20;i++)
{
f[i]=(i-1)*(f[i-1]+f[i-2]);
}
return ;
}
int c(int x, int y){
int n=x, m=y;
int sum=1,a=1,b=1;
for(int i=1;i<=y;i++) {
a*=n;
n--;
b*=m;
m--;
}
sum=a/b;
return sum;
}
int main(){
int N,M;
init();
while(scanf("%d%d",&N,&M)!=EOF)
{
cout<<c(N,M)*f[M]<<endl;
}
return 0;
}
方法二:通項公式 D(n)=n!*(1/2!-1/3!+1/4!- 1/5!+ ··· ··· +((-1)(n-1))/(n-1)!+((-1)n)/n! )
對通項先進行簡單變形:
C(n,m)D(m) = (n!/(m!(n-m)!))D(m) = n!(1/2!-1/3!+1/4!- 1/5!+ ··· ··· +((-1)(m-1))/(m-1)!+((-1)m)/m! )/(n-m)!
#include <cstdio>
#include <iostream>
#include <cstring>
typedef long long ll;
using namespace std;
long long f[22];
int c(int n){
ll sum=1;
for(int i=1; i<=n; i++)
sum*=i;
return sum;
}
int main(){
int N,M;
while(scanf("%d%d",&N,&M)!=EOF)
{
ll a=c(N), sum=0, b=c(N-M);
for(int i=2; i<=M; ++i){
a/=i;
if(i%2==0)
sum+=a;
else
sum-=a;
}
cout<<sum/b<<endl;
}
return 0;
}
本文内容參考自:
http://blog.csdn.net/yangyuhao0408/article/details/50971170