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

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

【問】
f:id:noriharu-katakura:20211105213236j:plain

【解】
$(1)$

積の法則から $3^n$ 通り.

$(2)$

ボールに区別がなく, 区別された $3$ つの箱に入るボールの個数だけを問題にするので,

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

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

$\displaystyle{ {}_{n+2}\mathrm{C}_{2} = \frac{(n+2)(n+1)}{2}}$

通り.

$(3)$

※ 箱は区別されないので, 番号のついたボールを $1$ つ, $2$ つ, $3$ つの順列を考慮しないグループに分けるやり方がそれぞれ何通りかを考察すればよい.

$n$ 個のボールが $1$ つの箱にすべて入る場合は $1^n = 1$ 通りしかない.

※ スターリング数で書けば, $S(n,1) = 1$

$n$ 個のボールが $2$ つの区別された箱に入る (ボールが入らない箱を許す) 場合は, $2^{n}$ 通りある. これから, $1$ つの箱にすべて入る $2$ 通りを除外して, $2$ つの箱のどちらにもボールが入る場合は, $2^{n} -2$ 通りとなる. $2$ つの箱は区別しないので, $2!$ で割って, $2^{n-1} -1$ 通りとなる.

※ スターリング数で書けば, $S(n,2) = 2^{n-1} -1$

$n$ 個のボールが $3$ つの区別された箱に入る (ボールが入らない箱を許す) 場合は, $3^n$ 通りある. $2$ つ以下の箱にボールがすべて入る場合は, $3 \times 2^n$ 通りある. $1$ つの箱にすべてボールが入る場合は, $3$ 通りなので, 包除原理を適用して, $3$ つのどの箱にもボールが入るのは,