プレゼント交換で誰も自分の品を引かない並べ方（完全順列）

5 人でプレゼント交換をします。全員が他人の品を引き当てる並び方は、120 通りのうち 44 通り。

自分の品を引く人が 1 人もいない並べ方を完全順列といいます。撹乱順列、あるいは英語で derangement とも呼ぶ^[1]。

定義と小さい場合

$1$ から $n$ までの番号を並べ替えて、$k$ 番目に $k$ が来ないようにします。この並べ方の総数を $D_n$ と書く。

$n=1$ では、1 を 1 番目に置くしかないので 0 通り。$n=2$ では 21 の 1 通りだけです。

$n=3$ は 231 と 312 の 2 通り。123、132、213、321 は、どこかに固定された数が残ります。

図で青いままの並びが完全順列です。24 通りを一巡すると、9 通りだけが残る。

例：4 人の 9 通りを書き出す

$n=4$ の完全順列をすべて並べます。

どの並びも、$k$ 番目が $k$ になっていません。手で確かめられる最後の大きさが、この $n=4$ です。

包除原理で求める

数え上げの道具は余事象と包除原理。「誰も自分のものを引かない」の反対から攻めます。

$i$ 番の人が自分のものを引く並べ方の集合を $A_i$ とします。$i$ を固定して残りを自由に並べるので、$n(A_i)=(n-1)!$ 通り。

2 人を固定すれば $(n-2)!$、3 人なら $(n-3)!$ と続きます。固定する人の選び方が ${}_n{\mathrm{C}}_k$ 通りあるので、包除原理の各項は次の形になる。

$${}_n{\mathrm{C}}_k\times (n-k)!=\frac{n!}{k!}$$

符号を交互に入れかえて足すと、少なくとも 1 人が自分のものを引く場合の数が出ます。

例：4 人で式を追う

$n=4$ で計算します。全体は $4!=24$ 通り。

1 人固定が $4\times 3!=24$、2 人固定が $6\times 2!=12$、3 人固定が $4\times 1!=4$、4 人固定が $1\times 0!=1$。

$$24-12+4-1=15$$

少なくとも 1 人が自分のものを引くのが 15 通り。全体から引いて $24-15=9$ 通りになります。書き出した 9 通りと合いました。

一般の公式

同じ計算を $n$ で書くと、階乗の逆数が交互に並ぶ形になります^[1]。

$$D_n=n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots +\frac{(-1{)}^n}{n!}\right)$$

$n=4$ なら $24\times \left(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}\right)=24\times \frac{3}{8}=9$。

括弧の中は、$1$ 番目の項から順に足し引きするだけです。項が増えるほど値が落ち着いていく。

2 つの漸化式

公式を毎回展開するより、前の値から次を作るほうが速い場面もあります。漸化式は 2 通り知られています^[2]。

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

$$D_n=n{D}_{n-1}+(-1{)}^n$$

前者は場合分けから導けます。$1$ 番の人が引いた品の番号を $k$ とすると、$k$ の選び方が $n-1$ 通り。

そのうえで、$k$ 番の人が $1$ を引く場合は残り $n-2$ 人の完全順列、引かない場合は残り $n-1$ 人の完全順列に対応します。だから $D_{n-2}+D_{n-1}$ を掛ける。

例：漸化式で 6 人まで

$D_1=0$、$D_2=1$ から順に作ります。

$D_3=2(D_2+D_1)=2(1+0)=2$。$D_4=3(D_3+D_2)=3(2+1)=9$。

$D_5=4(D_4+D_3)=4(9+2)=44$。$D_6=5(D_5+D_4)=5(44+9)=265$。

もう一つの漸化式でも確かめます。$D_5=5D_4+(-1{)}^5=45-1=44$。同じ値になりました。

確率はほぼ一定になる

$n$ が増えると、完全順列の確率 $D_n/n!$ はある値に近づきます。

$n=4$ で $9/24=0.375$、$n=5$ で $44/120\approx 0.367$、$n=6$ で $265/720\approx 0.368$。

人数を増やしても 0.368 あたりから動きません。この値は $1/e$ で、およそ 36.8 パーセント^[1]。

人数が 3 人でも 100 人でも、確率は 3 分の 1 と 5 分の 2 のあいだに収まる。直感に反する結果として、よく引かれる例です。

例：ちょうど何人かが自分のものを引く

「誰も引かない」だけでなく、「ちょうど $k$ 人が引く」も数えられます。

自分のものを引く $k$ 人を選び、残りの $n-k$ 人が完全順列になればよい。

$${}_n{\mathrm{C}}_k\times D_{n-k}$$

5 人でちょうど 2 人が自分のものを引くのは、${}_5{\mathrm{C}}_2\times D_3=10\times 2=20$ 通り。確率は $20/120=1/6$ です。

例：全部の場合を足すと元に戻る

検算になります。$k$ を 0 から 5 まで動かして足すと、$5!$ に戻るはず。

$44+5\times 9+10\times 2+10\times 1+5\times 0+1\times 1=44+45+20+10+0+1=120$。

確かに 120 になりました。$D_0=1$ と決めておくと、この足し算がきれいに閉じる。

例：ちょうど 1 人だけ

5 人でちょうど 1 人が自分のものを引くのは ${}_5{\mathrm{C}}_1\times D_4=5\times 9=45$ 通り。

完全順列の 44 通りより多い。「誰も引かない」より「1 人だけ引く」のほうが起こりやすいという結果です。

手紙と封筒の問題

この問題は 18 世紀にニコラス・ベルヌーイとオイラーが扱いました^[2]。宛名を書いた封筒に手紙を無作為に入れる形で語られます。

$n$ 通の手紙をでたらめに封筒へ入れて、1 通も正しく入らない確率はいくらか。答えが人数によらずほぼ一定になる点が、当時から驚きとして受けとめられていた。

同じ問題が、席替え、プレゼント交換、帽子のとり違えなど、いろいろな衣装で出てきます。

よくある誤り

完全順列は、包除原理と漸化式の両方が使える手ごろな題材です。どちらの道でも同じ値に着くことを、$n=4$ か $n=5$ で一度確かめておく。

参考文献

^[1] が定義と公式と極限、^[2] が 2 つの漸化式と数表と歴史、^[3] がプレゼント交換の形での例、^[4] と ^[5] が導出に使う包除原理です。