プレゼント交換会の数学～完全順列～ - みをつくしのひとりよがり

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

問題

　 $n$ 人が参加するクリスマス会でプレゼント交換をおこなう．それぞれの参加者が，自分が用意したプレゼントには当たらないように配りたい．

(1) $n = 4$ のとき，このようなプレゼントの配り方は何とおりあるか？

(2) $n$ 人のときにおけるプレゼントの配り方を $D_n$ とおりとする．数列 $\{ D_n \}$ は，以下の漸化式を満たす．これを示せ．

　 $D_1 = 0, \ D_2 =1,$

　 $D_n = (n-1) (D_{n-1} + D_{n-2}) \ \ (n \geqq 3)$

(3) 数列 $\{ D_n \}$ の一般項は，以下のように与えられる．これを示せ．

　 $D_n = \begin{cases} 0 \ \ (n=1) \\ \\ \displaystyle{ \sum_{k=2}^n \frac{(-1)^k}{k!} n! } \ \ (n \geqq 2) \end{cases}$

まずは，(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) \cdot D_{n-1}$ とおりとなります．

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

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

f:id:miwotukusi:20141102161644p:plain

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

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

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

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

$n=1$ の場合は，自明として示す．
$n=2, \ n=3$ の場合は，素直に代入をして式を満たすことを示す．
$n \geqq 4$ の場合について， $k-2, \ k-1$ の場合を仮定して， $k$ の場合を示す．

という流れになります．

補足(2014/11/15)

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

f:id:miwotukusi:20141115150751p:plain

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

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

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

問題