有名なパズル？がある。[br][br]「ｎ通の封筒に１枚の手紙を入れて出したい。手紙にも、封筒にもｎ個の宛先がかいてあるのだが、[br]封筒と手紙の宛先がすべて不一致になるような入れ方は何通りか」[br][br]という、[b]封筒違い問題[/b]と言われているものだ。[br]言い換えると、１からｎの数を並べるときに、[br]左からどの順番の数を見ても[b][color=#0000ff]番号と数が一致しない並べ方[/color][/b][br][b][size=200][size=150][color=#0000ff]不一致状態、乱れた数列、攪乱順列[/color][/size][/size][/b]になっていることから、[br][b][color=#0000ff][size=150][size=200]乱列[/size][/size][/color][/b]と呼ばれたりもする。[br][br][b]モンモール[/b]さんが1708 年に、n ＝ 13の場合に出題したものを、[br]あの偉大な数学者[b]オイラー[/b]さんが解いたという話も見聞きします。[br]真偽はともかく、オイラー関数の式を展開すると、以下にのべることにつながり、[br]さらに、順列を確率にしたときの値がオイラーとつながりのあるマクローリン級数展開と関連します。[br]。。。。。。[br][br]それはさておき、[br]具体的に調べてみよう。[br]ｎ＝１なら０通り。[br]ｎ＝２なら「２１」の１通り。[br]ｎ＝３なら、「２３１，３１２」の２通り。[br]ｎ＝４なら、「２１４３，２３４１，２４１３，[br]　　　　　　３１４２，３４１２，３４２１，[br]　　　　　　４１２３，４３１２，４３２１」の９通り。[br]このくらいならなんとかなるが、ｎ＝５以上では神経衰弱になってきそうだ。[br]そこで、救いの神の登場だ。[br][b][color=#0000ff][size=150]包含と排除の原理（包除原理、Principle of Inclusion and Exclusion, 略してPIE)[br][/size][/color][/b]を使って考えてみよう。[br][br]と言ってもPIEって何？[br]という人向けに確認しよう。[br][br][b][size=150]＜PIEとは何か＞[br][br][/size][/b]全体集合の中に対象の集合がある。[br]それら対象の集合に含まれない要素数を求める原理がPIEだ。[br]・集合が１個のとき[br][color=#0000ff]　[b]NotA[/b][b]＝|U|-|A|[/b][br][/color]　=n(U)-n(A)[br]・集合が２個のとき[br]　集合Uの中のAでもBでもない個数を出すには集合の個数n(集合)を使うと、[br][color=#0000ff]　[b]NotAB＝|U|-|A∪B|[/b][br][/color]　=n(U) - {n(A)+n(B)-n(A∩B)}=[b]n(U)- n(A)-n(B)+ n(A∩B)[/b]となるのは小中で学んでいるね。[br]・集合が３個のとき[br]　集合Cを追加すると、Cのうち、AでもBでもないものdiff=n(not(A∪B)∩C))を取り除く。[br]　NotABのUをCに、他を他∩Cに置き換えると、[br][b]　diff=n(C) - {n(A∩C)+n(B∩C)-n(A∩B∩C)}=n(C)- n(A∩C)-n(B∩C)+ n(A∩B∩C)だね。　[br][/b][b][color=#0000ff]NotABC＝|U|-|A∪B[b]∪C[/b]|[br][/color][/b] =NotAB-diff=n(U)- n(A)-n(B)+ n(A∩B)-(n(C)- n(A∩C)-n(B∩C)+ n(A∩B∩C))[br] [b]=n(U)- n(A)-n(B)-n(C)+ n(A∩B)+ n(A∩C) +n(B∩C)- n(A∩B∩C)[br][/b]・集合が４個のとき[br]　集合Dを追加すると、diff=n(not(A∪B∪C)∩D)を取り除くために、[br]　NotABCのUをDに、他を他∩Dに置き換える。[br]　[b]diff=n(D)- n(A∩D)-n(B∩D)-n(C∩D)+ n(A∩B∩D)+ n(A∩C∩D) +n(B∩C∩D)- n(A∩B∩C∩D)[br]　[color=#0000ff]NotABCD[/color][b][color=#0000ff]＝|U|-|A∪B[b]∪C[b][b][color=#0000ff]∪D[/color][/b][/b][/b]|[br][/color][/b][/b] =NotABC-diff=n(U)- n(A)-n(B)-n(C)+ n(A∩B)+ n(A∩C) +n(B∩C)- n(A∩B∩C)[br] -(n(D)- n(A∩D)-n(B∩D)-n(C∩D)+ n(A∩B∩D)+ n(A∩C∩D) +n(B∩C∩D)- n(A∩B∩C∩D)) [br] [b]= n(U)- n(A)-n(B)-n(C)-n(D)+ n(A∩B)+ n(A∩C) +n(B∩C)+n(A∩D)+n(B∩D)+n(C∩D)[br] - n(A∩B∩C)- n(A∩B∩D)- n(A∩C∩D) -n(B∩C∩D)+ n(A∩B∩C∩D))[br] =n(U)- Σn(X) +Σn(X∩Y)-Σn(X∩Y∩Z)+Σn(X∩Y∩Z∩P)[br][/b][br]・集合がN個のときの[br][color=#0000ff][b][size=200] PIEの一般化[/size][/b][/color][br][b][color=#0000ff][size=150][size=200] Notどれか=u(U)+Σ(-1)[sup]p[/sup]Σn(ΠX[sub]p[/sub])[br] [/size][/size][/color][/b]（Πはp個の集合の積集合でその組み合わはnCp個ある。符号は−１のp乗。[br]このように、個数を１個ずつ増やしている。[br]これは証明とは言えないが、[b]数学的帰納法で証明できるでしょう[/b]。だから、証明は省略。[br][br]ぜんぜん簡単に見えないかもしれないので、使い方を小さい順に確認しよう。[br][b]全体集合をm個すべての順列 m! [/b]としよう。[br]対象とする集合の要素数は番号と数が一致している順列だ。[br]だから、[br][b][color=#0000ff]n(A)は番号１が一致している順列 = (m-1)!、[br]n(B)は番号２が一致している順列 = (m-1)!、[br]n(A∩B）は番号１と２が一致している順列 = (m-2)!, ..、[br]n(A∩B∩C)は番号１，２，３が一致している順列 = (m-3)!, .....[br][/color][/b]という意味に読み替えよう。[br]すると、集合の重なりが少ないほど、一致する指定が少ないので、その他のけたは,ただの順列になる。[br]このように、[b]集合の個数を順列の個数に読み替えていこう。[br][/b][br]・集合が１個なら「１」の順列。[br] 乱列は、数字１の順列になり、全体の順列も１だから１通りの差は０。[br][b][color=#0000ff]・集合が２個なら「１２」の順列。[br]　乱列は数字１２の順列から（１が一致する場合数と２が一致する場合数）をひき２つ一致の場合たす。[br]　2!ー(1+1)+1=1通り。[br][/color][/b]・集合が３個なら「１２３」の順列。[br] 乱列＝全順列ー(123のどれか１個一致)＋(123のどれか２個一致)ー(123の３個一致)[br]　＝3!ー3×2!＋3×1!ー１＝６ー６＋３−１＝2通り。[br]・集合が４個なら「1234」の順列。[br] 乱列＝全順列ー(1個一致)＋(2個一致)ー(3個一致)＋(4個一致)[br]　＝4!- 4C1×3! + 4C2×2! - 4C3×1! + 4C4×0! = 24 - 4×6＋6×2 - 4 +1=9通り。[br][b] [color=#0000ff] （ここで、（ｋ個一致）はnCk×(n-k)!と気づく。） [br][/color][/b]・[b]集合が５個[/b]なら、[br] 乱列＝5! - 5C1×4! + 5C2×3! - 5C3×2! + 5C4×1! - 1 = 5C3×3! - 5C2×2! + 5C1×1!- 1[br][b][color=#0000ff]　　（ここで、（ｋ個一致）はnC(n-k)×(n-k)!＝nPkと気づく。最初の２項は相殺されることも気づく。）[br][/color][/b] ＝[b][color=#0000ff]5P3- 5P2+5P1-1[/color][/b]=60 - 20 + 5 -1 = 44通り。 [br]・[b]集合が６個なら、乱列＝[color=#0000ff]6P4 - 6P3 + 6P2 - 6P1 + 1[/color] [/b]= 265通り。[br]・[b]集合が７個なら。乱列＝[color=#0000ff]7P5 - 7P4 + 7P3 - 7P2 + 7P1 - 1[/color][/b]= 1854通り。[br]・集合がN個の一般化　乱列＝nP[sub]n-2[/sub] - nP[sub]n-3[/sub]+....(-1)[sup]n-i[/sup] nP[sub]n-i[/sub] +(-1)[sup]n-1[/sup]nP[sub]1[/sub]+(-1)[sup]n[/sup] = [b]Σ(-1)[sup]n-i[/sup] nP[sub]n-i[/sub] (2 <=i<=n)[/b][br] 乱列= [math]n!\sum_{k=2}^n\frac{\left(-1\right)^k}{k!}[/math] 分配法則でｎ!でまとめるとこうなる。[br]　もともとは、[b][color=#0000ff]数列nP[sub]n-2、[/sub]nP[sub]n-3 [/sub],....., nP[sub]1[/sub],１ にー＋を交互つけた和[/color][/b]のことだね。[br]　マクローリン展開を知っている人は[br]　[math]e^x=1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+..............[/math]を思い出すでしょう。[br]　すると、極限としては、[b][size=200][color=#0000ff]乱列→n! e[sup]-1[/sup][/color][/size][sup][/sup][/b][br]となるね。[br]地道に神経衰弱をくり返して書き出す作業の[b]限界突破[/b]ができる。[br]また、乱列数を分子として、n!を分母にすると、[br]乱列になる確率が約e[sup]-1[/sup]＝0.367879（約37％）にすぐに近づく！[br]すばらしい！

[color=#9900ff][b][size=200]質問：この発想で、ｎけたの乱列数をもとめるコードはどうすれば作れるでしょうか。[br][/size][/b][/color][br]n！でまとめて、分数形を使ってΣを先にやると分数の和に階乗をかけることになる。[br]あまりプログラミング向きではないですね。[br]permutationsで文字列として作り出すのではなく、ただのnPrの計算だね。[br]だから、itertoolsではなくて、mathパッケージでperm(n,r)でnPrが計算できることを確認しよう。[br]からこれでやろう。[br]pnPn-2からnP0まで符号を入れ替えながら合計したい。[br][b]だから、perm(n,n-x)のｘに2からnをいれて符号をつけたリストを作り、それをsumすればよいね。[br][br][size=200][color=#0000ff]オイラーに敬意を表して、ｎの乱列数は関数Eu(n)としました。[br][/color][/size][/b][br][color=#0000ff]#[In] Python[br]#===============================================[br]# サイズｎの乱列関数En(n)[br]from math import perm[br]def Eu(n):[br]return[b] [u]sum([(-1)**x * perm(n,n-x) for x in range(2,n+1)])[br][/u][/b]#==============結果===========[br]for i in range(1,10):[br] print(f"Eu({i}) = {Eu(i)} ",end=",")[br]#===============================================[br][OUT][br]Eu(1) = 0 ,Eu(2) = 1 ,Eu(3) = 2 ,Eu(4) = 9 ,Eu(5) = 44 ,Eu(6) = 265 ,Eu(7) = 1854 ,Eu(8) = 14833 ,Eu(9) = 133496 ,[/color]

動的にみるとどうなるだろう。[br][br]Eu(1) = 0 ,Eu(2) = 1 ,Eu(3) = 2 ,Eu(4) = 9 ,Eu(5) = 44 ,Eu(6) = 265 ,Eu(7) = 1854 ,Eu(8) = 14833[br]Eu(3)=2=1*3-1[br]Eu(4)=9=2*4+1[br]Eu(5)=44=9*5-1[br]ここから、[color=#0000ff][b][size=200]Eu(n)=Eu(n-1)*n+(-1)[sup]n[/sup][/size][/b][/color]という面白い関係に気づく。[br]実際,[br]Eu(6)=Eu(5)*6+1=44*6+1=265で合ってる。[br][br]でも、これでは、符号が交互になってしまう。[br][br]そこで公差をとってみた。[br]うまくいかない。[br]差ではなく和をやってみよう。[br]Eu(1)+Eu(2)=1[br]Eu(2)+Eu(3)=3[br]Eu(3)+Eu(4)=11[br]おっ44の約数がきたね。44=Eu(5)=11*4=(Eu(3)+Eu(4))*(5-1)となってる。[br]これから、[color=#0000ff][b][size=200]Eu(n)=(Eu(n-2)+Eu(n-1))*(n-1)[/size][/b][/color]が予想できる。[br]実際に、[br]Eu(6)=265=(9+44)*5=53*5=265。よさそうですね。[br][br]

さっきは[br]動的に考えることで、[br]２種類の漸化式ができた。[br]最後にできた方の意味づけを考えてみよう。[br][br][b][size=150]EU(n)=(EU(n-2)+EU(n-1))*(n-1)[br][/size][/b][br]これはこの式のままではないけれど、中学入試などにもでるストーリー化がある。[br]それを確認しておこう。[br]たとえば、[br][br][color=#0000ff][b][size=200]EU(4)=(EU(2)+EU(3))*3[br][/size][/b][/color][br]箱１から箱４までに玉１から玉４までが番号不一致で入っているとしよう。[br]ここから箱４がない状態に遡ってみる。[br]どうするか？[br]箱４に入っている玉は１，２，３の３通りあるので、とりあえず１番としよう。[br]このとき、１番の箱の中を見たとき、[br][b]箱１に入っている玉の番号は４番か４番でないかの２タイプがあるね。[br][/b][br][b]・箱１が玉４番であるタイプA[br][/b]箱４の玉１と箱１の玉４を入れ替えると[br][b]箱４は玉４でいいけど、箱１が玉１になるので、１個一致パターンになってしまう。[br][/b]しかし、箱４と箱１を撤去すると、のこり２箱は不一致になっているはずだ。[br]つまり、２箱不一致状態には合格している。[br][br][b]・箱１が玉４番でないタイプB[br][/b]箱４の玉１と玉４のある箱ｘ（１でない）の玉４を入れ替えると[br][b]箱４は玉４で、箱ｘ（１でない）が玉１になるので箱１から箱３まで３箱不一致パターンに合格してる。[br][/b][br]つまり、さかのぼると、[br]４箱不一致パターンの先祖は、箱４の玉番号で３分の１に絞り込める。[br]それが箱４の玉の番号の箱に入っている玉の番号で[br]２タイプ（タイプA２箱不一致かタイプB３箱不一致）に絞れる。[br]絞ったとしても場合の数はそれぞの乱列数だけある。[br][br]ということは、EU(4)は(EU(2)+EU(3))*(4-1)でがすべて尽くせることになるね。[br][br]逆に、箱が少ない段階をもとにして、箱４の番号不一致状態がすべて作れるはずだ。[br]タイプA）[br]箱１に玉１を入れて、箱２，３は不一致状態にしたとしょう。[br]ここに箱４に玉４を入れて追加したあと箱１と箱４の玉交換で４箱不一致ができるね。EU(２）個できる。[br]箱１ではなく、箱２，箱３でも同様だから、EU(2)*3の４箱不一致が作れる。[br]タイプB）[br]３箱不一致のときに箱１の玉を取り出して箱４に入れて、玉４を代わりに入れる。EU(3)個できる。[br]取り出す箱を、１番でなはく、２番，３番と変えられるからEU(3)*3の４箱不一致を作ることができる。[br][br]以上をあわせて、EU(2)*3+EU(3)*3がEU(4)になるね。[br]