1から4までの番号がついた箱とボールがある。すべての箱にそれぞれボールを1個ずつ入れるとき、箱の番号とボールの番号がすべて異なるような入れ方は何通りあるか。これは完全順列の問題です。

1. 問題の内容

1から4までの番号がついた箱とボールがある。すべての箱にそれぞれボールを1個ずつ入れるとき、箱の番号とボールの番号がすべて異なるような入れ方は何通りあるか。これは完全順列の問題です。

2. 解き方の手順

完全順列の総数を求める問題です。

n個のものを並べ替えて、どの要素も元の位置にないように並べる場合の数をモンモール数または攪乱数と呼び、$D_n$ で表します。

$D_n$の漸化式は次の通りです。

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

また、

$D_1 = 0$

$D_2 = 1$

$D_3 = 2$

$D_4 = 9$

今回は$n=4$の場合なので、

箱が4つでボールが4つのとき、どの箱にも同じ番号のボールを入れない入れ方を求めます。

$D_4 = (4-1)(D_3 + D_2) = 3(2 + 1) = 3 \times 3 = 9$

または、包除原理を使って計算することもできます。

全体の場合の数は4! = 24通りです。

1つ以上の箱に同じ番号のボールが入る場合の数を引いていきます。

A_i を i番目の箱にi番目のボールが入る事象とすると、求める場合の数は

$|A_1 \cup A_2 \cup A_3 \cup A_4|$

を全体から引いたものです。

$|A_i| = (4-1)! = 3! = 6$

$|A_i \cap A_j| = (4-2)! = 2! = 2$ (i != j)

$|A_i \cap A_j \cap A_k| = (4-3)! = 1! = 1$ (i != j != k)

$|A_1 \cap A_2 \cap A_3 \cap A_4| = (4-4)! = 0! = 1$

$|A_1 \cup A_2 \cup A_3 \cup A_4| = \binom{4}{1}3! - \binom{4}{2}2! + \binom{4}{3}1! - \binom{4}{4}0! = 4 \times 6 - 6 \times 2 + 4 \times 1 - 1 \times 1 = 24 - 12 + 4 - 1 = 15$

求める場合の数は $4! - 15 = 24 - 15 = 9$ 通りです。

3. 最終的な答え

9通り