攪乱順列とは・・・

質問

攪乱順列とはなんでしょうか。またその個数の求め方の公式（包含と排除の原理）が解りません。

なんとなく「順列で動かないものが1つもないもの」のようなことはわかります。

包含と排除の原理
n(U)-n(P1∪P2∪P3∪・・・・∪Pn)
=n(U)-Σn(Pi)+Σn(Pi∩Pj)-Σn(Pi∩Pj∩Pk)+・・・・+(-1)^n*n(P1∩P2∩P3∩・・・・∩Pn)
=n!*(1-1/1!+1/2!+1/3!+・・・・・+(-1)^n*1/n!)

結論として上の最後の行だけ覚えればいいのでしょうか。i,j,kが何かもよくわかりません。1-Pバーのようなことも書いてありますがちょっと理解できません。

回答No.1

zk43 · ベストアンサー

Piはiが一致する順列全体の集合です。（集合の要素は順列）
残りのn-1個はどのような並びでも良いので(n-1)!個あります。
ただし、この中にはi以外に一致する場合も含みます。
Σn(Pi)=n×(n-1)!=n!です。（和はi=1,2,…,nで取る）
Pi∩Pjはi,jが一致する順列全体の集合で、残りのn-2個はどのような
並びでも良いので(n-2)!個あります。ただし、他に一致する数字が
あっても構いません。
Σn(Pi∩Pj)は1≦i＜j≦nの範囲でi,jを動かしたときの和で、
nC2=n(n-1)/2個の和を取っています。
その和は、n(n-1)/2×(n-2)!=n!/2です。
つまり、２個の数字が一致する順列全体の個数を数えています。
後も同様で、Pi∩Pj∩Pkはi,j,kが一致する順列全体の集合で、残りの
n-3個はどのような並びでも良く、(n-3)!個あります。
Σn(Pi∩Pj∩Pk)は1≦i＜j＜k≦nの範囲でi,j,kを動かしたときの和
で、nC3=n(n-1)(n-2)/3!個の和を取っています。その和は、
n(n-1)(n-2)/3!×(n-3)!=n!/3!です。
以下同様に続ければ、質問文にあるような式になります。
n!で割ってn→∞にすれば1/eに収束し、撹乱順列になる確率が1/eに
収束するというもので、これは有名なものです。
また、
n(P1∪P2∪P3∪・・・・∪Pn)
=Σn(Pi)-Σn(Pi∩Pj)+Σn(Pi∩Pj∩Pk)-・・・・
+(-1)^(n-1)*n(P1∩P2∩P3∩・・・・∩Pn)
は包含定理（シルベスターの定理）と呼ばれるものですが、n=2のとき
のn(P1∪P2)=n(P1)+n(P2)-n(P1∩P2)を示して、数学的帰納法により
証明できます。
（n(P1∪P2)=n(P1)+n(P2)-n(P1∩P2)はP1∪P2を重ならない部分に分割
して、A∩B=φならばn(A∪B)=n(A)+n(B)という性質を使って証明でき
ます。）
n(P1∪P2∪P3∪・・・・∪Pn)はどれかの数字が一致する、すなわち撹
乱順列ではない順列の個数で、したがって、これを全体の順列の個数n!
から引けば撹乱順列全体の個数が求まります。
規則的な式なので憶えやすいとは思います。

回答No.3

koko_u_

>攪乱順列とはなんでしょうか。またその個数の求め方の公式（包含と排除の原理）が解りません。
この問題を dandy_lion さんが何時間考えたのか補足して下さい。

>結論として上の最後の行だけ覚えればいいのでしょうか。
覚えても恐らく役には立たないでしょう。

前回の時にも書きましたが、「どれを覚えておけば良いか」以前に問題に対する思考が圧倒的に不足しているように見受けられます。

文句ばっかり言っても削除されそうなので、アドバイスらしきことも書こう。
・一足飛びに一般解を得るのではなく、n = 1,2,3,... と具体的に求めましょう。n が小さければノートに場合の数を列挙すれば誰でも求められるはずです。
・求めた具体例に規則性がないか考えましょう。階差数列をとるとか、色々習いませんでしたか？
・それらしき「一般解」を予測したら、帰納法で証明できないか試みましょう。
・その他思い付くことを色々

包含と排除の原理についても、n が小さければベン図を書くことぐらい誰でもできるはずです。

質問欄にそれらの思考の跡が書かれていないので、私は 「問題分を読む」→ 「難しそうなので解答欄を読む」→「理解できないので OKWave に書く」といった作業を dandy_lion さんがしているのではないかと勘繰ってしまうのですよ。

回答No.2

zk43

見落としましたが、撹乱順列とは何か？というのがありましたね。
撹乱順列とは1,2,…,nを並べ変えたときに、1番目に1が来ない、
2番目に2が来ない、・・・、n番目にnが来ないような順列のことです。
例えば、1,2,3の順列で、3,1,2は撹乱順列ですが、3,2,1は2番目に2
が来ているので撹乱順列ではありません。
もう少し形式的に書くと、
1,2,…,nの順列a1,a2,…,anで任意のi=1,2,…,nについてai≠iである
ような順列のことです。
ai=iとなっているときはi番目に出会いを持つ、などともいいます。