ノリの悪い日記

古今東西の映画、ポピュラー音楽、その他をいまここに交錯させながら随想します。

陥没地帯 (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 つのどの箱にもボールが入るのは,

 3^n - 3 \times 2^n + 3

となる. 3 つの箱は区別しないので, 3! で割って,

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

通りとなる.

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

以上より, 3 つの箱すべてにボールが入る場合, 2 つの箱すべてにボールが入る場合, 1 つの箱にすべてのボールが入る場合をすべて加えて,

\displaystyle{\frac{3^{n-1} + 1}{2} -2^{n-1} + 2^{n-1} -1 + 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-2, 2m+1, 2m + 1),
\\ \quad \cdots, (2, 3m-2, 3m-2), (0, 3m, 3m)

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

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

通りである.
//