東京大学 1996年度後期・理系数学後期第1問解答・解説

問題

$n$ 個のボールを3箱へ入れる。空箱を許す。

(1) ボールも箱も区別するときの総数。

(2) ボールは区別せず箱を区別するときの総数。

(3) ボールを区別し箱を区別しないときの総数。

(4) $n = 6 m$ で、ボールも箱も区別しないときの総数。

出典：東京大学 1996年度後期日程第2次学力試験後期・理系後期第1問

区別する場合は選択・非負整数解で数える。(3)は箱の置換による同一視を固定される入れ方で平均し、(4)は $0 ≦ x ≦ y ≦ z$ の整数解を直接加える。

各ボールに3箱の選択肢があるので

3^{n} .

各箱の個数を $x, y, z$ とすると $x + y + z = n$ の非負整数解の数であり

\frac{( n + 1 ) ( n + 2 )}{2} .

まず3箱を区別した $3^{n}$ 通りを箱の6個の置換で分類する。恒等置換は $3^{n}$ 通りを固定する。3個の互換の各々に固定される入れ方は、動かない1箱に全ボールを入れる1通りだけである。2個の3-cycleに固定される入れ方はない。従って求める数は

\frac{3 ^{n} + 3}{6} .

箱の個数を $0 ≦ x ≦ y ≦ z$ 、 $x + y + z = 6 m$ とする。 $x$ は $0$ から $2 m$ まで動き、固定した $x$ に対し

x ≦ y ≦ ⌊ \frac{6 m - x}{2} ⌋ .

従って総数は

x = 0 \sum 2 m (⌊ \frac{6 m - x}{2} ⌋ - x + 1) .

$⌊(6 m - x) /2 ⌋ = 3 m - ⌈ x /2 ⌉$ 、また $\sum_{x = 0}^{2 m} ⌈ x /2 ⌉ = m (m + 1)$ だから、整理して

(2 m + 1) (3 m + 1) - m (2 m + 1) - m (m + 1) = 3 m^{2} + 3 m + 1.