陥没地帯 (272) - ノリの悪い日記

$1996$ 年, 東大理科後期の問題. 基本的なことを考察させる問題なので, とりあげることにした. 問 $(1)$ は重複順列, 問 $(2)$ は重複組合せ, 問 $(3)$ は, (第 $2$ 種) スターリング数, 問 $(4)$ は自然数の分割に関連している問である.

【問】

【解】
$(1)$
積の法則から $3^n$ 通り.

$(2)$
ボールに区別がなく, 区別された $3$ つの箱に入るボールの個数だけを問題にするので, 重複組合せの問題.

$x_1 + x_2 + x_3 = n$
$x_1, x_2, x_3 \geq 0$

の解の組の個数を求めることと同じで,

$\begin{align} {}_{3}\mathrm{H}_{n} &={}_{n+3-1}\mathrm{C}_{n}\\ & = {}_{n+2}\mathrm{C}_{2}\\ &= \frac{(n+2)(n+1)}{2}\\ \end{align}$

通り.

$(3)$
$n$ 個のボールが $1$ つの箱にすべて入る場合は $1$ 通り.

$n$ 個のボールが $2$ つの区別されない箱にすべて入る場合は,

$\displaystyle{ \frac{2^n - 2}{2!} = 2^{n-1} -1}$

通り.

$n$ 個のボールが $3$ つの区別されない箱に入る場合は,

$\displaystyle{ \frac{3^n - 3\cdot (2^n-2) - 3}{3!} =\frac{3^{n-1} + 1}{2}-2^{n-1}}$

通り. 以上すべて加えて,

$\displaystyle{\frac{3^{n-1} + 1}{2} -2^{n-1} + 2^{n-1} -1 + 1 \\= \frac{3^{n-1} + 1}{2}}$

通りとなる.

※ $n$ 個のボールが $2$ つの区別されない箱にすべて入る場合一通りに対して, $2$ つの区別された箱の場合は結局 $6$ 倍多く数えており, これは箱に $3$ つとも入る場合と変わりない. したがってもっと簡単に,

$\displaystyle{ \frac{3^n - 3}{3!} +1 \\=\frac{3^{n-1} -1}{2}+1 \\=\frac{3^{n-1} + 1}{2}}$

でよかった.

$(4)$

問 $(2)$ の結果に, $n =6m$ を代入すると,

$\displaystyle{ \frac{(6m+2)(6m+1)}{2}= 18m^2 + 9m + 1}$

となるが, このうち, 解が $2$ 個以上同じになる重解をもつ組を, 箱の並びを考慮しないで列挙してみると,

$(0,0, 6m), (1,1,6m-2), \cdots, \\ (2m, 2m, 2m), (2m+1, 2m+1, 2m -2 ), \\ \quad \cdots, (3m-1, 3m-1, 2), (3m, 3m,0)$

となる. したがって, 箱を区別する場合には, $2$ 個の解が一致するものが, $3 \cdot 3m = 9m$ 組, $3$ 個とも一致するものが $1$ 組存在する. したがってボールも箱も区別しない場合は,

$\displaystyle{ \frac{18m^2}{3!} + \frac{9m}{3} + 1 = 3m^2 + 3m + 1}$

通りである.
//