数学A 完全順列･攪乱順列･モンモール数 問題 2 解説

方針・初手

自分のコートを受け取った人を「固定されている人」と考える。

[ア] は「ちょうど2人が自分のコートを受け取り、残り3人は全員自分以外のコートを受け取る」場合である。したがって、まず自分のコートを受け取る2人を選び、残った3人について完全順列を数えればよい。

[イ] は5人全員が自分以外のコートを受け取る場合なので、5個の完全順列の個数を求めればよい。

解法1

まず、3人全員が自分以外のコートを受け取る場合を考える。

3人を $A,B,C$ とする。$A$ が受け取れるコートは $B$ または $C$ のコートである。

(i)

$A$ が $B$ のコートを受け取るとき、$B$ は $C$ のコート、$C$ は $A$ のコートを受け取るしかない。

(ii)

$A$ が $C$ のコートを受け取るとき、$C$ は $B$ のコート、$B$ は $A$ のコートを受け取るしかない。

よって、3人の完全順列は

$$ 2 $$

通りである。

したがって [ア] は、まず自分のコートを受け取る2人を5人から選び、残り3人を完全順列にすればよいから、

$$ {}_5C_2 \times 2 = 10 \times 2 = 20 $$

である。

次に [イ] を求める。5人全員が自分以外のコートを受け取る場合の数、すなわち5個の完全順列の個数を包除原理で求める。

5人のコートの渡され方全体は

$$ 5! $$

通りである。

ここから「少なくとも1人が自分のコートを受け取る」場合を除く。特定の $k$ 人が自分のコートを受け取るように固定すると、残り $5-k$ 人への渡し方は $(5-k)!$ 通りである。

包除原理より、5人全員が自分以外のコートを受け取る場合の数は

$$ \begin{aligned} 5! - {}_5C_1 4! + {}_5C_2 3! - {}_5C_3 2! + {}_5C_4 1! - {}_5C_5 0! &= 120 - 5 \cdot 24 + 10 \cdot 6 - 10 \cdot 2 + 5 \cdot 1 - 1 \\ &= 120 - 120 + 60 - 20 + 5 - 1 \\ &= 44 \end{aligned} $$

よって [イ] は

$$ 44 $$

である。

解法2

完全順列の漸化式を用いてもよい。$n$ 人全員が自分以外のコートを受け取る場合の数を $D_n$ とする。

よく知られた完全順列の漸化式

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

を用いる。

初期値は

$$ D_1=0,\qquad D_2=1 $$

である。したがって、

$$ D_3=2(D_2+D_1)=2(1+0)=2 $$

である。

[ア] では、自分のコートを受け取る2人を選び、残り3人を完全順列にすればよいから、

$$ {}_5C_2D_3=10 \cdot 2=20 $$

である。

また、

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

であり、

$$ D_5=4(D_4+D_3)=4(9+2)=44 $$

となる。

よって [イ] は

$$ 44 $$

である。

解説

この問題は「自分のコートを受け取らない」という条件を、完全順列として処理するのが基本である。

[ア] では「2人だけが自分のコートを受け取る」ので、最初にその2人を選ぶ必要がある。その後、残り3人については全員が自分以外のコートを受け取るため、3人の完全順列になる。

[イ] は5人全員の完全順列である。包除原理で数える方法が最も直接的であり、完全順列の漸化式を知っていればさらに短く計算できる。

答え

[ア]

$$ 20 $$

[イ]

$$ 44 $$