1から $n$ までの番号が書かれた $n$ 枚のカードを、区別しない3つの箱に入れる。 (1) 2つ以上の箱にカードが入るような入れ方の総数を求める。 (2) カードの入れ方の総数を求める。

1. 問題の内容

1から $n$ までの番号が書かれた $n$ 枚のカードを、区別しない3つの箱に入れる。

(1) 2つ以上の箱にカードが入るような入れ方の総数を求める。

(2) カードの入れ方の総数を求める。

2. 解き方の手順

(1) 全ての入れ方の総数から、1つの箱に全てのカードが入る場合の数を引けばよい。

カードの入れ方の総数を求める。各カードについて、3つの箱のいずれかに入れることができるので、入れ方は $3^n$ 通り。

ただし、箱は区別しないので、全て1つの箱に入れる場合は1通り。

2つの箱に入れる場合は、まず $n$ 枚のカードを2つのグループに分け、その2つのグループを箱に入れることになる。2つのグループに分ける方法は、$2^n$ 通りあるが、全てのカードが1つのグループに入ってしまう場合が2通りあるので、それを引いて $2^n - 2$ となる。

しかし、箱は区別しないので、($2^n - 2$) / 2 = $2^{n-1} - 1$ となる。

したがって、2つの箱に入れる場合は、$2^{n-1} - 1$ 通り。

3つの箱に入れる場合は、$3^n$ 通り。ただし、箱は区別しないので、順列を考慮する必要がある。しかし、箱が空である場合も考慮すると複雑になる。

カードの入れ方の総数を考える。

各カードに対して、3つの箱のいずれかに入れることができるので、$3^n$ 通り。

しかし、箱は区別しないので、このままでは数えすぎになる。

$n$ 枚のカードを3つの箱に入れる場合の数を $S(n, k)$ (第2種スターリング数)とすると、

$S(n, 1) + S(n, 2) + S(n, 3)$ となる。

$S(n, 1) = 1$

$S(n, 2) = 2^{n-1} - 1$

$S(n, 3) = \frac{1}{6}(3^n - 3 \times 2^n + 3)$

したがって、$1 + (2^{n-1} - 1) + \frac{1}{6}(3^n - 3 \times 2^n + 3) = \frac{1}{6}(3^n + 3 \times 2^{n-1} - 3 \times 2^n + 6) = \frac{1}{6}(3^n - 3 \times 2^{n-1} + 6)$ となる。

次に、2つ以上の箱にカードが入る場合の数を考える。これは、1つの箱に全てのカードが入る場合を除けばよい。

全てのカードを1つの箱に入れる方法は、1通り。したがって、カードの入れ方の総数から1を引けばよい。

したがって、$\frac{1}{6}(3^n - 3 \times 2^{n-1} + 6) - 1 = \frac{1}{6}(3^n - 3 \times 2^{n-1})$

カードの入れ方の総数は、$3^n$通り。

2つ以上の箱にカードが入る場合の数は、全体の数から1つの箱に全て入る場合を引けばよい。

箱が区別できないので、1つの箱に全て入る場合は1通り。したがって、全体の入れ方の総数から1を引いた値が答えになる。

カードの入れ方の場合の数。

各カードについて3つの箱のどれかに入れることができるので、$3^n$ 通り。ただし、箱は区別しないので、空の箱があってもよい。箱を区別する場合は、$3^n$ 通りだが、区別しない場合は、

(1) 1つの箱に入れる場合：1通り

(2) 2つの箱に入れる場合：$2^{n-1}-1$

(3) 3つの箱に入れる場合：$\frac{1}{6}(3^n-3\times2^n+3)$

したがって、合計は、$1 + 2^{n-1}-1 + \frac{1}{6}(3^n-3\times2^n+3) = 2^{n-1}+\frac{1}{6}(3^n-3\times2^n+3) = \frac{1}{6}(3^n - 3\times2^{n-1} + 3)$

2つ以上の箱にカードが入る場合の数は、$1 + (2^{n-1} - 1) = 2^{n-1}$。

これは間違い。

カードの入れ方の総数 - 1 = $\frac{3^n+3}{6} - 1 = \frac{3^n - 3}{6} = \frac{3(3^{n-1}-1)}{6}$

$\frac{3^{n}+3\times2^{n-1}-3\times2^{n}+6}{6} - 1$

ウ: $3^n - 1$

エ: $\frac{3^n+3}{6}$

3. 最終的な答え

ウ: $3^n - 1$

エ: $\frac{3^n+3}{6}$