誤配列式の導出と応用について
誤排問題は,更列問題とも呼ばれ,組合せ数学における問題の一つである.その研究は18世紀にさかのぼることができ、当時は数学者のニコラ・バーヌーリとオラに研究されていたため、歴史的にはバーヌーリ・オラの誤装封筒問題とも呼ばれていた.この問題には多くの具体的なバージョンがあります.例えば、手紙を書くときにn通の手紙をn個の異なる封筒に入れ、封筒を全部間違えた場合は何種類ありますか.例えばn人がそれぞれ1枚ずつカードを書いて贈り合うとしたら、何種類の贈り方がありますか?これらの古典的なテーマはすべて典型的な間違い問題である.
上记の间违いの问题に対する简単な绍介を见たことがあることを信じて、みんなもそれに対していくつか初歩的な理解があって、まとめると、1つのnつの要素の配列を考えて、もし1つの配列の中ですべての要素が自分の元の位置の上でないならば、このような配列は元の配列の1つの间违いと称して、nつの要素の间违いの列数はD(n)と记します.では、このような配列D(n)には何種類あるのでしょうか.私たちは一歩一歩分析します.
まず、D(n)に対して、1~nというn個の要素がずれているので、第1の要素1に対して、現在可能な位置は(n-1)個であり、もしそれが第kの要素の位置にあるならば、第kの要素にとって、その位置は2つの可能性がある-第1の要素1以外の位置にある.従って、次の配列は、n−1要素の誤配列、すなわちD(n−1)に相当する.第2に、第1の要素1の位置にあるので、配列D(n)に2つの要素が位置を見つけると、次のキューは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)で割る!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−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/5!+ ··· ··· +((-1)^(n-1))/(n-1)!+((-1)^n)/n! ).
これにより,誤り問題に関する2つの公式を簡単な導出により得た.
今、私たちは具体的な問題を具体的に分析して、間違いの公式がどのようにコードに転化して試験の中で実際に出会った問題を解決するかを理解して、私たちはここでHDU Online Judgeの上の1つの問題が新郎を試験することを例にして、問題はこのようにします:
問題を読むと、この問題の本質は配列組合せC(n,m)と誤配列m要素D(m)の積を解くことであることがわかります.そのため、この問題のコードも非常に簡単で、以下に2つのACプログラムを提供します.
#方法1:繰返し式--D(n)=(n-1)*(D(n-1)+D(n-2))[D(1)=0,D(2)=1]
ここでは、タイトルに基づいて変形することができます.
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)!
これで誤配列式についての推論と簡単な応用が完成しました~!
上记の间违いの问题に対する简単な绍介を见たことがあることを信じて、みんなもそれに対していくつか初歩的な理解があって、まとめると、1つのnつの要素の配列を考えて、もし1つの配列の中ですべての要素が自分の元の位置の上でないならば、このような配列は元の配列の1つの间违いと称して、nつの要素の间违いの列数はD(n)と记します.では、このような配列D(n)には何種類あるのでしょうか.私たちは一歩一歩分析します.
まず、D(n)に対して、1~nというn個の要素がずれているので、第1の要素1に対して、現在可能な位置は(n-1)個であり、もしそれが第kの要素の位置にあるならば、第kの要素にとって、その位置は2つの可能性がある-第1の要素1以外の位置にある.従って、次の配列は、n−1要素の誤配列、すなわちD(n−1)に相当する.第2に、第1の要素1の位置にあるので、配列D(n)に2つの要素が位置を見つけると、次のキューは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)で割る!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−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/5!+ ··· ··· +((-1)^(n-1))/(n-1)!+((-1)^n)/n! ).
これにより,誤り問題に関する2つの公式を簡単な導出により得た.
今、私たちは具体的な問題を具体的に分析して、間違いの公式がどのようにコードに転化して試験の中で実際に出会った問題を解決するかを理解して、私たちはここでHDU Online Judgeの上の1つの問題が新郎を試験することを例にして、問題はこのようにします:
問題を読むと、この問題の本質は配列組合せC(n,m)と誤配列m要素D(m)の積を解くことであることがわかります.そのため、この問題のコードも非常に簡単で、以下に2つの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;
}ここでは、タイトルに基づいて変形することができます.
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<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;
}これで誤配列式についての推論と簡単な応用が完成しました~!