読者です 読者をやめる 読者になる 読者になる

理系男子の独り善がり

仕事や生活に役立ちそうな(実際に役立つかは別として)数学・物理ネタをつらつらと書いていこうと思ってます.

プレゼント交換会の数学~完全順列~

今回は,完全順列を考えます.別名,攪乱順列とも呼ばれるもので,こちらの方が意味を理解しやすいようにも思います.問題として考えることにします.メインは場合の数ですが,数列や数学的帰納法の内容も含んでいます.

 

問題

f:id:miwotukusi:20141102170055p:plain

 

まずは,(1)から

これは,順当に数え上げることを考えます.ただ,やみくもに羅列すると,重複したり,条件を満たしていないものを含めてしまったりします.「辞書式」に挙げていくのがよいかと思います.

4人をA,B,C,Dとし,それぞれが配られるプレゼントの組を(A,B,C,D)のように表すとする(この場合,各自が自分の用意したプレゼントを配られている).題意を満たす組合せは,以下の9とおりである.

(B,A,D,C),(B,C,D,A),(B,D,A,C),(C,A,D,B),(C,D,A,B),(C,D,B,A),(D,A,B,C),(D,C,A,B),(D,C,B,A)

 

今回のメインは(2)

証明すべき対象は漸化式ですが,完全順列の「並べ方」を考えることで証明をおこないます.参考書やWebなどで,アプローチの仕方が多少異なるものもあります.ここでは,「すでに完全順列になっているn-1個の並びに,n番目を追加する」ことから考えていくことにします.

たとえば,小問(1)で4つの文字の並びを考えていますが,3つ(A,B,C)の並びに4番目(D)を加えることを考えてみてください.D[1],D[2]は,具体例を挙げて示せばよいです.

i)すでに完全順列になっているn-1個の並びに,n番目を追加する場合

このままでは,n番目に数「n」があることになるので,完全順列になりません.数「n」をここから動かすために,前にあるn-1個の数のいずれかと交換します.どのn-1個の数と交換しても,完全順列ができあがります.交換する数の選び方は,n-1とおりですから,この場合の並べ方の数は(n-1)・D[n-1]とおりとなります.

ii)1個だけ「かぶった」数のあるn-1個の並びに,n番目を追加する場合

上の場合だけでは,このパターンが漏れてしまいます.交換する数自体が「k番目にk」となっている場合です.このkの選び方はn-1とおりですから,この場合の並べ方は(n-1)・D[n-2]とおりとなります(n-2個の数は完全順列になっていることに注意).

f:id:miwotukusi:20141102161644p:plain

 

2個以上「かぶった」数がある場合は,n番目の数とは1個しか交換できないので完全順列にはなりません.よって,これで場合分けは網羅したことになります.

 

(3)は計算するだけとはいえ…

一般項の形が与えられているので,漸化式を用いて正しいことを示します.つまり,数学的帰納法を用いることになります.「隣が成り立つこと」を示すことがメインですが,「先頭」も大事だということを忘れないでください.

いまの問題では,一般項がn≧2で成り立つ形になっているので,

  • n=1の場合は,自明として示す.
  • n=2,n=3の場合は,素直に代入をして式を満たすことを示す.
  • n≧4の場合について,n-2,n-1の場合を仮定して,nの場合を示す.

という流れになります.

 

補足(2014/11/15)

上で書いている内容を表にしておきます.

f:id:miwotukusi:20141115150751p:plain

 

以下に,n≧4のときの計算過程を細かめに示しておきます.Σ記号の上限や指数,階乗の計算をきちんとおこなわないといけません.おおまかには,2か所出てくるΣの和を取る範囲を一度k=2~n-2に合わせておき,余った項をまたΣに取り込むという離れ業を使います.

Σ記号は「kについての和」を計算しているので,nは定数項扱い(わかりにくければ,Σ記号の外へ出してしまう)になることにも注意が必要です.

f:id:miwotukusi:20141102175255j:plain

 

ちなみに,一般項の式の両辺をn!で割ると,左辺のD[n]/n!は「すべての配り方のうち,自分の用意したプレゼントには当たらない配り方になる確率」を求めていることになります.一度,どこかで勉強してないと,解くのは難しい問題かもしれませんね.