完全順列(プレゼント交換)

方針

解答

⓪ 発想 — どう考え始めるか。 「全員が自分の以外」を正面から数えるのは難しい。

そこで補集合に切り替える。「少なくとも $1$ 人が自分のを受け取る」場合を、全体から引く。

ただし「$1$ 人が自分の」という場合どうしは重なり合う。重なりを足し引きする包除で調整する。

否定の数え上げは、補集合と包除の合わせ技で攻める。その定跡を総合する問題だ。

全員が自分以外を受け取る配り方を、包除の考え方で数える。「自分のものを受け取ってしまう」という『まずい』場合を引いていく。

特定の $k$ 人が自分のプレゼントを受け取り、残り $4-k$ 人は自由、という配り方は ${}_4{\mathrm{C}}_k\times (4-k)!$ 通り。これを $k=1,2,3,4$ について、符号を「引く→足す→引く→足す」と交互にして全体から差し引く。

$$4!-{}_4{\mathrm{C}}_1\cdot 3!+{}_4{\mathrm{C}}_2\cdot 2!-{}_4{\mathrm{C}}_3\cdot 1!+{}_4{\mathrm{C}}_4\cdot 0!$$

$$=24-4\times 6+6\times 2-4\times 1+1\times 1=24-24+12-4+1=9(\text{通り})$$

符号が交互になるのは、「1人が自分のを受け取る場合」を引くと「2人が受け取る場合」を引き過ぎるので足し戻し、するとまた「3人」を戻し過ぎる…という調整が続くからだ。

まとめ:4人くらいなら、実際に樹形図で書き出しても9通りと確かめられる。「Aが受け取る相手はB, C, Dの3通り、その1つ1つに対して残りの配り方が3通り」で $3\times 3=9$ 通り、という数え方もできる。

発展 — 一歩先へ。 $9$ 通りの中身を「入れかわりの形」で分類すると、構造が見えてくる。全員が自分以外を受け取る配り方は、じつは $2$ つの型しかない。

$1$ つは「$2$ 人ずつのペアが交換する」型。$4$ 人を $2$ 人ずつのペアに分ける方法は $3$ 通りで、各ペアの中で交換するだけだから、この型は $3$ 通り。

もう $1$ つは「$4$ 人がひとつの輪になって順送りする」型。$\mathrm{A}\to \mathrm{B}\to \mathrm{C}\to \mathrm{D}\to \mathrm{A}$ のような一巡の並べ方は $(4-1)!=6$ 通り。合わせて $3+6=9$ で、数え上げの結果とぴたり一致する。

この「交換のペア」と「順送りの輪」への分解は、並べかえ(置換)をサイクルという部品に分ける見方で、あらゆる並べかえがサイクルの組み合わせに分解できる。完全順列とは「長さ $1$ のサイクル(動かない人)がない置換」のことだ、と言い直せる。

別解

別解 — 小さい人数から漸化式で積み上げる(得意な人向けの視点)。 包除を使わず、人数を増やしながら数える。

$n$ 人の完全順列の個数を $D_n$ とする。$1$ 人だけなら自分に配るしかなく $D_1=0$、$2$ 人なら入れ替える $1$ 通りで $D_2=1$。

$n$ 人のとき、$1$ 番の人が受け取る相手を $k$ とすると、$k$ の選び方は $n-1$ 通り。このとき「$k$ 番も $1$ 番のものを受け取る(=$1$ と $k$ が交換する)」なら、残り $n-2$ 人の完全順列で $D_{n-2}$ 通り。「$k$ 番は $1$ 番のを受け取らない」なら、残り $n-1$ 人を「それぞれ決まった $1$ 席を避けて」座らせる完全順列とみなせて $D_{n-1}$ 通り。

まとめると

$$D_n=(n-1)\left(D_{n-1}+D_{n-2}\right).$$

順に計算すると $D_3=2(D_2+D_1)=2(1+0)=2$、$D_4=3(D_3+D_2)=3(2+1)=9$。本解の包除と同じ $9$ 通りだ。