トップ› 九州大学› 1993年› 文系第1問

九州大学 1993年文系第1問解説

方針・初手

集合の要素をいくつかの空でない部分集合に分割する問題であり、これは第2種スターリング数として知られる題材である。 (1)と(2)では、要素の個数の配分パターン（たとえば「2個のグループが1つと、1個のグループがいくつか」など）を列挙し、それぞれの場合の数を組み合わせを用いて計算する。 (3)では、各要素を2つの部屋に割り当てるという視点からアプローチし、重複や条件を満たさないものを除外する。 (4)では、$n+1$ 番目の要素が単独でグループを作るか、それとも既存のグループに加わるかで場合分けを行い、漸化式を導出する。

解法1

(1)

$n$ 個の数字を $n-1$ 個の空でない部分に分割する。各部分の要素数は少なくとも 1 であるため、$n$ 個の要素を $n-1$ 個の部分に分けるときの要素数の配分は、「2個の要素からなる部分が1つと、1個の要素からなる部分が $n-2$ 個」となる。したがって、求める分割の方法の数は、どの2つの数字を同じ部分に入れるかを選ぶ方法の数に等しい。 $n$ 個の数字から2個を選ぶ組み合わせの数であるから、

$$S_n(n-1) = {}_n\mathrm{C}_2 = \frac{n(n-1)}{2}$$

(2)

$n$ 個の数字を $n-2$ 個の空でない部分に分割する。要素数の配分として、次の2つの場合が考えられる。

(i) 3個の要素からなる部分が1つと、1個の要素からなる部分が $n-3$ 個の場合 $n$ 個の数字から同じ部分に入る3個を選ぶ方法の数に等しいから、

$${}_n\mathrm{C}_3 = \frac{n(n-1)(n-2)}{3 \cdot 2 \cdot 1} = \frac{n(n-1)(n-2)}{6}$$

(ii) 2個の要素からなる部分が2つと、1個の要素からなる部分が $n-4$ 個の場合 $n$ 個の数字から、2個のペアを2組作る方法の数に等しい。まず1組目のペアを選び（${}_n\mathrm{C}_2$ 通り）、残りから2組目のペアを選ぶ（${}_{n-2}\mathrm{C}_2$ 通り）。このとき、2つのペアのグループには区別がないため $2!$ で割る必要がある。

$$\frac{{}_n\mathrm{C}_2 \times {}_{n-2}\mathrm{C}_2}{2!} = \frac{\frac{n(n-1)}{2} \times \frac{(n-2)(n-3)}{2}}{2} = \frac{n(n-1)(n-2)(n-3)}{8}$$

(i) と (ii) は互いに排反であるから、これらを足し合わせて、

$$\begin{aligned} S_n(n-2) &= \frac{n(n-1)(n-2)}{6} + \frac{n(n-1)(n-2)(n-3)}{8} \\ &= \frac{n(n-1)(n-2)}{24} \{ 4 + 3(n-3) \} \\ &= \frac{n(n-1)(n-2)(3n-5)}{24} \end{aligned}$$

(3)

$1$ から $n$ までの $n$ 個の数字を、A, B という区別のある2つの部屋に入れることを考える。各数字につき A または B の2通りの入れ方があるため、総数は $2^n$ 通りである。ここから、A または B のどちらかの部屋が空になる場合（すべての数字がAに入る、またはすべての数字がBに入る）の2通りを引く。

$$2^n - 2$$

これにより、2つの空でない部屋 A, B に分割する方法の数が求まる。問題では分割された部分（グループ）の区別はないため、A と B の入れ替えによる重複を解消するために 2 で割る。

$$S_n(2) = \frac{2^n - 2}{2} = 2^{n-1} - 1$$

(4)

$n+1$ 個の数字 $\{1, 2, \dots, n, n+1\}$ を $k$ 個の空でない部分に分割する方法を、特定の数字「$n+1$」に注目して次の2つの場合に分ける。

(i) 数字 $n+1$ が単独で1つの部分をなす場合このとき、残りの $1$ から $n$ までの $n$ 個の数字は、$k-1$ 個の空でない部分に分割されている。その分割の方法は $S_n(k-1)$ 通りである。

(ii) 数字 $n+1$ が他の数字と同じ部分に含まれる場合まず、$1$ から $n$ までの $n$ 個の数字を $k$ 個の空でない部分に分割する。この方法は $S_n(k)$ 通りである。次に、数字 $n+1$ を、この $k$ 個の部分のいずれか1つに追加する。追加先となる部分の選び方は $k$ 通りある。したがって、この場合の分割の方法は $k S_n(k)$ 通りである。

(i) と (ii) は同時に起こることはなく互いに排反であり、これ以外に分割のパターンは存在しない。和の法則より次が成り立つ。

$$S_{n+1}(k) = S_n(k-1) + k S_n(k)$$

解説

「第2種スターリング数」の定義とその性質を問う典型的な漸化式・場合の数の問題である。(1)と(2)は具体的な要素の構成パターンを過不足なく書き出し、場合の数の基本である「組み合わせの計算」と「重複度の解消（区別のない組の扱い）」を正しく行えるかを問うている。(3)はグループ分け問題における標準的な解法である「先にグループを区別して考え、最後にその並び順で割る」というアプローチを用いると簡潔に処理できる。(4)の漸化式は、特定の1要素の動向に注目して場合分けをするという、組み合わせ論の証明において非常に重要な発想を用いている。