4つの箱と4つのボールがあり、それぞれに1から4までの番号が付けられています。 (1) 1番の箱に1番のボールを入れる場合、残りの箱に箱の番号と異なる番号のボールを入れる方法は何通りあるか。 (2) すべての箱に、箱の番号と異なる番号のボールを入れる方法は何通りあるか。

1. 問題の内容

4つの箱と4つのボールがあり、それぞれに1から4までの番号が付けられています。

(1) 1番の箱に1番のボールを入れる場合、残りの箱に箱の番号と異なる番号のボールを入れる方法は何通りあるか。

(2) すべての箱に、箱の番号と異なる番号のボールを入れる方法は何通りあるか。

2. 解き方の手順

(1) 1番の箱に1番のボールを入れると、残りの3つの箱と3つのボールについて考えます。

残りの箱を2, 3, 4とし、ボールを2, 3, 4とします。

このとき、どの箱も自分の番号のボールを入れてはいけません。

* 2の箱に3を入れる場合、3の箱には4、4の箱には2を入れるしかありません。 (2->3, 3->4, 4->2)

* 2の箱に4を入れる場合、3の箱には2、4の箱には3を入れるしかありません。 (2->4, 3->2, 4->3)

したがって、1番の箱に1番のボールを入れる場合、残りの箱に箱の番号と異なる番号のボールを入れる方法は2通りです。

(2) これは完全順列の問題です。4つの箱と4つのボールに対して、どのボールも自分の番号の箱に入らないようにする方法の数を求めます。これは攪乱順列（かくらんじゅんれつ）と呼ばれ、n個の要素の完全順列の数を $D_n$ と表します。

$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$

$D_4 = 4! (\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!})$

$D_4 = 24 (1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24})$

$D_4 = 24 (\frac{12 - 4 + 1}{24}) = 9$

別の考え方として漸化式を用いる方法もあります。

$D_1 = 0$

$D_2 = 1$

$D_3 = 2$

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

3. 最終的な答え

(1) 2通り

(2) 9通り