ノリの悪い日記

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

陥没地帯 (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

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

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

通り.

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

 n 個のボールが 2 つの区別された箱 A,  B に入る場合は, 2^{n} 通りあるが,  A または B の箱には入らない 2 通りを除外すると,  2^{n} -2 通り. 箱を区別しない場合には 2! で割って,  2^{n-1} -1 通りとなる.

 n 個のボールが 3 つの区別された箱  A, B, C に入る場合は, 3^n 通りある.  A または  B または  C にボールが入らない場合は,  3 \times 2^n - 3 通りある. したがって, どの箱にもボールが入る場合は,

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

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

\displaystyle{\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+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}

通りである.
//