パズルの国のアリス

ポーンたちのプレゼント交換(解答)

 最初の問題,つまり誰かに自分が持ってきたプレゼントが当たる確率は,組み合わせ論的確率論では比較的に馴染みの問題で,答えを知っている読者も多かろう。その解説から始めることにしよう。

 この問題に答えるには,英語でderangementと表現されるものを数え上げることが基本となる。derangementを英和辞典で引くと,「攪乱」や「混乱」という訳語が目につく。精神的な状況を表す「錯乱」や「発狂」という意味もあるらしいが,数学用語としては「攪乱列」や「乱列」という語を当てることが多いようだ。本稿では「乱列」という言葉を採用したい。乱列が何かというと,n個のものが並んでいるとき,それらを並べ直して,どれも前とは同じ位置に来ないようにする順列のことである。例えばA,B,C,Dの4つがABCDの順に並んでいた場合,それらを並べ直したCBDAはBが左から2番目にあって前と同じだから乱列とは言わない。DABCなら乱列である。n人のプレゼント交換により自分の用意したものが自分のところには来ないという結果,すなわち問題の余事象と,この乱列とが1対1に対応することは,自明だろう。

 n個の要素の乱列の数をDn)と書くことにしよう。nが小さい正の整数のときは,乱列をすべて書き出すことでDn)が容易に求まる。例えば,D(1)=0,D(2)=1,D(3)=2,D(4)=9である。実際にABCDの乱列をすべて書き出すと,BADC,BCDA,BDAC,CADB,CDAB,CDBA,DABC,DCAB,DCBAの9つだ。だがポーンの場合のようにn=8にもなると,重複や数え落としがないようにすべてを書き出すのは容易ではないから,組み合わせ論の出番になる。

 こういう場合に有効なのは「包除原理」である。英語ではinclusion-exclusion principleと呼ばれるもので,省略せずに包含排除原理と訳すこともあるようだ。これは,和集合の要素数や和事象の確率を計算するうえで不可欠な法則で,一番簡単な形の適用例は

#(AB)=(#A)+(#B)−#(AB

というものだ(#AAの要素数)。ABの要素数を知りたいときにABの要素数を足したのでは,ABに共通の要素を2重にカウントすることになるから,その分を引き戻しておけばよいという,もっともな話を法則化したにすぎない。ただ,集合が2つなら簡単だが,3つ以上あるときには複雑になる。一般式を書くなら,Fを有限個の有限集合の集まりとするとき

となる。複雑な式に見えるがF={AB}の場合は,上に書いたものと同じだから,慣れている人には何でもないと思う。

 といっても,こんな式は見たくないという読者もおられるだろうから,包除原理の考え方を用いてDn)をどのように計算するかを考えることにしよう。乱列を数えるにはそうでない列を数えて,全順列の個数n!から引けばよい。ある順列が乱列でないということは,1番目からn番目までのどこかに前と同じ人がいるということだ。1番目の人が同じである列はいくつあるだろうか? これは簡単だ。ほかのn−1カ所は勝手に並べてよいのだから(n−1)!個ある。同様に2番目が同じという列も(n−1)!個だ。だが,1番目からn番目までのどこかが前と同じという列が(n−1)!×nn!個あると考えるのは間違い。なぜなら2カ所が同じという列が2重に数えられているからだ。では,その分を引くことにしよう。1番目と2番目が同じという列は(n−2)!個,1番目と3番目が同じという列も(n−2)!個だから,2カ所で同じという列はその2カ所がどこの場合でも(n−2)!個ある。n個の位置から2カ所の選び方はnC2だけあるから,どこか2カ所が前と同じという列は延べで(n−2)!×nC2n!/2!個ある。そこでそれをn!から引いてn!(1−1/2!)でよいだろうか? おっと,実はこれでは引きすぎで,3カ所で同じという列がカウントされなくなってしまう。そこで3カ所で同じという列の延べ個数(n−3)!×nC3n!/3!を足すと,今度は4カ所で同じという列の分が足しすぎなのでその延べ個数n!/4!を引き……ということを一般に述べているのが式①だ。結局,どこかが前と同じ,すなわち乱列でないものの個数は

だから,その反対に乱列の個数 Dn)は

である。くじの引き直しが起こるのは乱列でない場合だから,その確率は

ということになる(この確率はDn)を用いて1−Dn)/n!とも書ける)。n=8の場合にこれを厳密に計算するのは,手計算では大変だろう。しかし,nが大きくなれば,Dn)/n!の値が1/eに急速に収束することに気がつけば,求める確率はだいたい1−1/e≈0.632であると簡単に計算できる。

 そもそも,上のDn)の式は具体的なnに対して乱列の個数を計算するのには向かない。そのためには上の式を変形して簡単に証明できる次の漸化式が便利だ。

Dn)=nDn−1)+(−1)n

これを使えば D(1)=0から始めて

D(2)=2×0+1=1, D(3)=3×1−1=2
 D(4)=4×2+1=9, D(5)=5×9−1=44

というふうにn!と同じくらいの手間で乱列の個数が計算できる。また,Dn)=(n−1)×(Dn−1)+Dn−2))という式も成り立つので,こちらを使ってもよいかもしれない。

 次の問題は,並び直したときに1回目と同じ順で隣り合う2人組が生じる確率だ。この場合も包除原理の考え方が基本となる。最初の撮影で並んだ順にポーンたちに番号を振り,彼らが1回目に1-2-……-nと並んでいたとしよう(n=8であるが,一般にnで考える)。2回目の撮影でも1-2という並びができていたとしたら,このような順列は何通りあるだろうか? 実は1-2をひとかたまりと考えれば1-2,3,4,……,nというn−1個のものを並べるのと同じだと気がつく。よって全部で(n−1)!通りだ。同様に2-3や3-4などの並びを含む順列の数もそれぞれ(n−1)!通りあるから,このどれかの並びを含む順列は延べで(n−1)×(n−1)!通りだが,乱列の場合と同じでこれでは多すぎる。同じ順で隣り合う2人が2カ所以上に同時に生じることがあるからで,その分を引かねばならない。同じ順で隣り合う2人が2組ある場合というのは,1-2-3のような3人のかたまりができている場合と1-2と4-5のように2人ずつのかたまりが2つできている場合があるが,冷静に考えるとどちらもn−2個のものを並べるのと同じだとわかる。対2組の選び方はn−1C2通りあるから,同じ順で隣り合う対が2組ある場合は延べで(n−2)!×n−1C2=(n−2)(n−1)!/2!通りある。先と同様に,これを引き,さらに同じ順で隣り合う対が3組ある場合を足し戻し,4組ある場合を引き……と進めていくと,結局,同じ順で隣り合う対を含まない順列の数をQn)と書けば

となる。これを変形すると

である。だから8人の場合,同じ順で隣り合う2人が生じる確率は1−Q(8)/8!=1−(D(8)+D(7))/8!であり,くじの引き直しが起こる確率よりもD(7)/8!だけ小さい。nが大きくなればDn−1)/n!≈1/(ne)→0だから,人数が多くなればくじの引き直しの場合との差は相対的には縮まっていき,1−1/eに収束する点は同じだが,収束はくじの引き直しの場合よりもずっと遅い。

問題はこちらです