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

散歩道にいつも見ているのとは別のイイギリがあることに初めて気がついた. どうして, いままで気がつかなかったんだろう.

前回の問題は, 実際に練習しないとなかなかコツや本当のところがわからない. $(3)$ のスターリング数は高校では教えないと思うんだが, 入試問題では出題されている.

まずは小手調べ. 年度は不明だが, 東京理科大の問題. この手の問題は山のようにある気がする.

【問】 $12$ 冊の異なる本を次のように分ける方法は何通りあるか.

$(1)$ $5$ 冊， $4$ 冊， $3$ 冊の $3$ 組に分けるのは, ( ) 通り.

$(2)$ $4$ 冊ずつ $3$ 人の子供に分けるのは, ( ) 通り.

$(3)$ $4$ 冊ずつ $3$ 組に分けるのは, ( ) 通り.

$(4)$ $8$ 冊， $2$ 冊， $2$ 冊の $3$ 組に分けるのは, ( ) 通り.

【解】
この種の問題にまごつかないようにするために, 「類別」という考え方に慣れておく必要がある. 「組」とは類のことで, 類を集めて類別 (類の集合) を作るには, 類の「異なるものだけを」集めてくる必要がある(類は類別=集合の要素だから). なお, 類別では類が空集合であることを許さない. 集合全体を互いに共通部分のない空でない部分集合によって分割することと, 集合を同値関係により類別することは等価である.

$(1)$
$12$ 冊の異なる本を $5$ 冊， $4$ 冊， $3$ 冊の類に類別するやり方は,

$\displaystyle{{}_{12}\mathrm{C}_{3}\times {}_{9}\mathrm{C}_{4}=27720}$

通りである.

この場合はこれでよいのだが, $(3)$ のケースは注意が必要なので, $(2)$ をとばして $(3)$ から説明する.

$(3)$
この場合は, $(1)$ と同じやり方で選択していくと同じ類が生じる場合があることに注意する. 類別を作るには, 異なる類だけを集める必要があるので,

$\displaystyle{\frac{1}{3!} {}_{12}\mathrm{C}_{4}\times {}_{8}\mathrm{C}_{4} =5775}$

通りである.

$(2)$
この場合は, 単に順列として処理すればよい.

$\displaystyle{{}_{12}\mathrm{C}_{4}\times {}_{8}\mathrm{C}_{4} =34650}$

通り.

$(4)$
これは, 類別の数である. 細かいようだが, 数字の小さい方から計算した方が楽である.

$\displaystyle{\frac{1}{2!} {}_{12}\mathrm{C}_{2}\times {}_{10}\mathrm{C}_{2} = 1485}$

通り. //

第 $2$ 種スターリング数 $S(n, k)$ とは, $n$ 個の異なるものを, $k$ 個の類に類別するやり方の総数のことである. 類の要素は $1$ つ以上必要で, 各類に含まれる要素の個数は異なっていてもよい.

次は, $2012$ 年の奈良女子大の問題.

【問】

【解】
$(1)$ ここでの「組」は, 学校のクラスぐらいの意味で使っているんだと思う. もし, そうだとしたら,

$\displaystyle{{}_{5}\mathrm{C}_{1}\times {}_{4}\mathrm{C}_{2} = 30}$

通り.

$(2)$ こちらは類別で同じ集合は除いて異なる集合だけを集めてこないといけない.

$\displaystyle{\frac{1}{2!} {}_{5}\mathrm{C}_{1}\times {}_{4}\mathrm{C}_{2} = 15}$

通り.

$(3)$ $3$ つに類別する方法は, $(2)$ で求めた他には, $\{3,1,1\}$ があり,

$\displaystyle{\frac{1}{2!} {}_{5}\mathrm{C}_{1}\times {}_{4}\mathrm{C}_{1} = 10}$

通りのやり方がある. したがって, $2$ つあわせて, $S(5,3) = 25$ 通り.

$(4)$
$n+1$ 人の生徒が $k$ 個の類に類別されているとき, その中の $1$ 人の生徒について考えると, 次の $2$ つの場合がある.

(a) その生徒が含まれている類には, その生徒 $1$ 人しかいない.
(b) その生徒が含まれている類には, 他の生徒がいる.

(a) の場合は, 類別のやり方は, $S(n, k-1)$ 通りある. (b) の場合, その生徒は $k$ 個の類のどれかに含まれているので, 類別のやり方は, $kS(n, k)$ 通りある. したがって,

$S(n+1, k) = S(n, k-1) + kS(n, k)$

が成立する.
//

$1997$ 年の長崎総合科学大の問題.

【問】

【解】
$(1)$
$\displaystyle{ {}_{7}\mathrm{C}_{1}\times {}_{6}\mathrm{C}_{2} \times {}_{4}\mathrm{C}_{2} = 630}$

通り.

※ 類別の数を求めるには, 「類別の型」に注目して形式的に処理する方法がある.

たとえば, この場合, 整数 $7$ を $3$ つの和因子へと分割すると,

$7 = 1 + 1 +5$
$7 = 1 + 2 +4$
$7 = 1 + 3 +3$
$7 = 2 + 2 +3$

の $4$ 通りあるが, このそれぞれの型を最初から, 形式的に

$1^25^1$ , $1^12^14^1$ , $1^13^2$ , $2^23^1$ と書く. そうすると, それぞれの類別の数は,

$\displaystyle{ \frac{7!}{(1!)^2(5!)^1(2!)(1!) }= 21}$

$\displaystyle{ \frac{7!}{(1!)^1(2!)^1(4!)^1(1!)(1!)(1!)}=105}$

$\displaystyle{ \frac{7!}{(1!)^1(3!)^2(1!)(2!)}=70}$

$\displaystyle{ \frac{7!}{(2!)^2(3!)^1(2!)(1!)}=105}$

上の合計, つまり $S(7,3)$ は $301$ になる.

$S(7,3)$ を求めるのに, 前の記事の問 $(3)$ の方法を使って,

$\displaystyle { S(7,3) \\= \frac{1}{3!}(3^7 - 3 \cdot 2^7 + 3) \\= 301}$

としても同じ結果が得られる.

したがって,

$(2)$

$3!S(7,3) = 1806$ 通り.

※ひとつの類別と $\{A, B, C\}$ の間には, $3!$ 個の全単射写像がある.

$(3)$

$S(7,3) = 301$ 通り.
//

2005 年神戸大の問題.

【問】

【解】
$(1)$
$\displaystyle{\frac{1}{3!} {}_{6}\mathrm{C}_{2}\times {}_{4}\mathrm{C}_{2} = 15}$

$(2)$
$\displaystyle{S_n \\= \frac{1}{n!} {}_{14}\mathrm{C}_{2}\times {}_{14-2\cdot 1}\mathrm{C}_{2} \times \cdots \times {}_{14-2(n-1)}\mathrm{C}_{2} \\= \frac{14!}{(2!)^nn!(14-2n)!} }$