乱列を関数EUで
１．封筒ちがい・乱列
有名なパズル？がある。
「ｎ通の封筒に１枚の手紙を入れて出したい。手紙にも、封筒にもｎ個の宛先がかいてあるのだが、
封筒と手紙の宛先がすべて不一致になるような入れ方は何通りか」
という、封筒違い問題と言われているものだ。
言い換えると、１からｎの数を並べるときに、
左からどの順番の数を見ても番号と数が一致しない並べ方
不一致状態、乱れた数列、攪乱順列になっていることから、
乱列と呼ばれたりもする。
モンモールさんが1708 年に、n ＝ 13の場合に出題したものを、
あの偉大な数学者オイラーさんが解いたという話も見聞きします。
真偽はともかく、オイラー関数の式を展開すると、以下にのべることにつながり、
さらに、順列を確率にしたときの値がオイラーとつながりのあるマクローリン級数展開と関連します。
。。。。。。
それはさておき、
具体的に調べてみよう。
ｎ＝１なら０通り。
ｎ＝２なら「２１」の１通り。
ｎ＝３なら、「２３１，３１２」の２通り。
ｎ＝４なら、「２１４３，２３４１，２４１３，
３１４２，３４１２，３４２１，
４１２３，４３１２，４３２１」の９通り。
このくらいならなんとかなるが、ｎ＝５以上では神経衰弱になってきそうだ。
そこで、救いの神の登場だ。
包含と排除の原理（包除原理、Principle of Inclusion and Exclusion, 略してPIE)
を使って考えてみよう。
と言ってもPIEって何？
という人向けに確認しよう。
＜PIEとは何か＞
全体集合の中に対象の集合がある。
それら対象の集合に含まれない要素数を求める原理がPIEだ。
・集合が１個のとき
NotA＝|U|-|A∪B|
=n(U)-n(A)
・集合が２個のとき
集合Uの中のAでもBでもない個数を出すには集合の個数n(集合)を使うと、
NotAB＝|U|-|A∪B|
=n(U) - {n(A)+n(B)-n(A∩B)}=n(U)- n(A)-n(B)+ n(A∩B)となるのは小中で学んでいるね。
・集合が３個のとき
集合Cを追加すると、Cのうち、AでもBでもないものdiff=n(not(A∪B)∩C))を取り除く。
NotABのUをCに、他を他∩Cに置き換えると、
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)だね。
NotABC＝|U|-|A∪B∪C|
=NotAB-diff=n(U)- n(A)-n(B)+ n(A∩B)-(n(C)- n(A∩C)-n(B∩C)+ n(A∩B∩C))
=n(U)- n(A)-n(B)-n(C)+ n(A∩B)+ n(A∩C) +n(B∩C)- n(A∩B∩C)
・集合が４個のとき
集合Dを追加すると、diff=n(not(A∪B∪C)∩D)を取り除くために、
NotABCのUをDに、他を他∩Dに置き換える。
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)
NotABCD＝|U|-|A∪B∪C∪D|
=NotABC-diff=n(U)- n(A)-n(B)-n(C)+ n(A∩B)+ n(A∩C) +n(B∩C)- n(A∩B∩C)
-(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))
= 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)
- n(A∩B∩C)- n(A∩B∩D)- n(A∩C∩D) -n(B∩C∩D)+ n(A∩B∩C∩D))
=n(U)- Σn(X) +Σn(X∩Y)-Σn(X∩Y∩Z)+Σn(X∩Y∩Z∩P)
・集合がN個のときの
PIEの一般化
Notどれか=u(U)+Σ(-1)pΣn(ΠXp)
（Πはp個の集合の積集合でその組み合わはnCp個ある。符号は−１のp乗。
このように、個数を１個ずつ増やしている。
これは証明とは言えないが、数学的帰納法で証明できるでしょう。だから、証明は省略。
ぜんぜん簡単に見えないかもしれないので、使い方を小さい順に確認しよう。
全体集合をm個すべての順列 m! としよう。
対象とする集合の要素数は番号と数が一致している順列だ。
だから、
n(A)は番号１が一致している順列 = (m-1)!、
n(B)は番号２が一致している順列 = (m-1)!、
n(A∩B）は番号１と２が一致している順列 = (m-2)!, ..、
n(A∩B∩C)は番号１，２，３が一致している順列 = (m-3)!, .....
という意味に読み替えよう。
すると、集合の重なりが少ないほど、一致する指定が少ないので、その他のけたは,ただの順列になる。
このように、集合の個数を順列の個数に読み替えていこう。
・集合が１個なら「１」の順列。
乱列は、数字１の順列になり、全体の順列も１だから１通りの差は０。
・集合が２個なら「１２」の順列。
乱列は数字１２の順列から（１が一致する場合数と２が一致する場合数）をひき２つ一致の場合たす。
2!ー(1+1)+1=1通り。
・集合が３個なら「１２３」の順列。
乱列＝全順列ー(123のどれか１個一致)＋(123のどれか２個一致)ー(123の３個一致)
＝3!ー3×2!＋3×1!ー１＝６ー６＋３−１＝2通り。
・集合が４個なら「1234」の順列。
乱列＝全順列ー(1個一致)＋(2個一致)ー(3個一致)＋(4個一致)
＝4!- 4C1×3! + 4C2×2! - 4C3×1! + 4C4×0! = 24 - 4×6＋6×2 - 4 +1=9通り。
（ここで、（ｋ個一致）はnCk×(n-k)!と気づく。）
・集合が５個なら、
乱列＝5! - 5C1×4! + 5C2×3! - 5C3×2! + 5C4×1! - 1 = 5C3×3! - 5C2×2! + 5C1×1!- 1
（ここで、（ｋ個一致）はnC(n-k)×(n-k)!＝nPkと気づく。最初の２項は相殺されることも気づく。）
＝5P3- 5P2+5P1-1=60 - 20 + 5 -1 = 44通り。
・集合が６個なら、乱列＝6P4 - 6C3 + 6P2 - 6P1 + 1 = 265通り。
・集合が７個なら。乱列＝7P5 - 7P4 + 7P3 - 7P2 + 7P1 - 1= 1854通り。
・集合がN個の一般化 乱列＝nPn-2 - nPn-3+....(-1)n-i nPn-i +(-1)n-1nP1+(-1)n = Σ(-1)n-i nPn-i (2 <=i<=n)
乱列= 分配法則でｎ!でまとめるとこうなる。
もともとは、数列nPn-2、nPn-3 ,....., nP1,１ にー＋を交互つけた和のことだね。
マクローリン展開を知っている人は
を思い出すでしょう。
すると、極限としては、乱列→n! e-1
となるね。
地道に神経衰弱をくり返して書き出す作業の限界突破ができる。
また、乱列数を分子として、n!を分母にすると、
乱列になる確率が約e-1＝0.367879（約37％）にすぐに近づく！
すばらしい！
e^xの級数展開を目でみよう
質問：この発想で、ｎけたの乱列数をもとめるコードはどうすれば作れるでしょうか。
n！でまとめて、分数形を使ってΣを先にやると分数の和に階乗をかけることになる。
あまりプログラミング向きではないですね。
permutationsで文字列として作り出すのではなく、ただのnPrの計算だね。
だから、itertoolsではなくて、mathパッケージでperm(n,r)でnPrが計算できることを確認しよう。
からこれでやろう。
pnPn-2からnP0まで符号を入れ替えながら合計したい。
だから、perm(n,n-x)のｘに2からnをいれて符号をつけたリストを作り、それをsumすればよいね。
オイラーに敬意を表して、ｎの乱列数は関数Eu(n)としました。
#[In] Python
#===============================================
# サイズｎの乱列関数En(n)
from math import perm
def Eu(n):
return sum([(-1)**x * perm(n,n-x) for x in range(2,n+1)])
#==============結果===========
for i in range(1,10):
print(f"Eu({i}) = {Eu(i)} ",end=",")
#===============================================
[OUT]
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 ,
乱列とe^(-1)
２．動的にみると
動的にみるとどうなるだろう。
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(3)=2=1*3-1
Eu(4)=9=2*4+1
Eu(5)=44=9*5-1
ここから、Eu(n)=Eu(n-1)*n+(-1)nという面白い関係に気づく。
実際,
Eu(6)=Eu(5)*6+1=44*6+1=265で合ってる。
でも、これでは、符号が交互になってしまう。
そこで公差をとってみた。
うまくいかない。
差ではなく和をやってみよう。
Eu(1)+Eu(2)=1
Eu(2)+Eu(3)=3
Eu(3)+Eu(4)=11
おっ44の約数がきたね。44=Eu(5)=11*4=(Eu(3)+Eu(4))*(5-1)となってる。
これから、Eu(n)=(Eu(n-2)+Eu(n-1))*(n-1)が予想できる。
実際に、
Eu(6)=265=(9+44)*5=53*5=265。よさそうですね。
３．漸化式を意味づけする
さっきは
動的に考えることで、
２種類の漸化式ができた。
最後にできた方の意味づけを考えてみよう。
EU(n)=(EU(n-2)+EU(n-1))*(n-1)
これはこの式のままではないけれど、中学入試などにもでるストーリー化がある。
それを確認しておこう。
たとえば、
EU(4)=(EU(2)+EU(3))*3
箱１から箱４までに玉１から玉４までが番号不一致で入っているとしよう。
ここから箱４がない状態に遡ってみる。
どうするか？
箱４に入っている玉は１，２，３の３通りあるので、とりあえず１番としよう。
このとき、１番の箱の中を見たとき、
箱１に入っている玉の番号は４番か４番でないかの２タイプがあるね。
・箱１が玉４番であるタイプA
箱４の玉１と箱１の玉４を入れ替えると
箱４は玉４でいいけど、箱１が玉１になるので、１個一致パターンになってしまう。
しかし、箱４と箱１を撤去すると、のこり２箱は不一致になっているはずだ。
つまり、２箱不一致状態には合格している。
・箱１が玉４番でないタイプB
箱４の玉１と玉４のある箱ｘ（１でない）の玉４を入れ替えると
箱４は玉４で、箱ｘ（１でない）が玉１になるので箱１から箱３まで３箱不一致パターンに合格してる。
つまり、さかのぼると、
４箱不一致パターンの先祖は、箱４の玉番号で３分の１に絞り込める。
それが箱４の玉の番号の箱に入っている玉の番号で
２タイプ（タイプA２箱不一致かタイプB３箱不一致）に絞れる。
絞ったとしても場合の数はそれぞの乱列数だけある。
ということは、EU(4)は(EU(2)+EU(3))*(4-1)でがすべて尽くせることになるね。
逆に、箱が少ない段階をもとにして、箱４の番号不一致状態がすべて作れるはずだ。
タイプA）
箱１に玉１を入れて、箱２，３は不一致状態にしたとしょう。
ここに箱４に玉４を入れて追加したあと箱１と箱４の玉交換で４箱不一致ができるね。EU(２）個できる。
箱１ではなく、箱２，箱３でも同様だから、EU(2)*3の４箱不一致が作れる。
タイプB）
３箱不一致のときに箱１の玉を取り出して箱４に入れて、玉４を代わりに入れる。EU(3)個できる。
取り出す箱を、１番でなはく、２番，３番と変えられるからEU(3)*3の４箱不一致を作ることができる。
以上をあわせて、EU(2)*3+EU(3)*3がEU(4)になるね。