離散数学・組合せ論の問題

考え方

$n$ 個の区別できるものを、区別しない空でない $k$ 個のブロックに分ける方法の数を第 $2$ 種スターリング数 $S(n,k)$ で表す。漸化式
$$S(n,k)=S(n-1,k-1)+kS(n-1,k)$$
は、特定の $1$ 人（ここでは A さん）に注目して、次の $2$ 通りに分けることから導かれる。

• A さんが $1$ 人だけのグループになる場合：残りの $6$ 人を $2$ グループに分ければよいので $S(6,2)$ 通り。
• A さんがほかの人と同じグループに入る場合：まず残りの $6$ 人を $3$ グループに分け（$S(6,3)$ 通り）、A さんをその $3$ グループのどれかに加える（$3$ 通り）。よって $3S(6,3)$ 通り。

求めるのは後者なので、答えは $3S(6,3)$ である。

$S(6,3)$ を漸化式で求める

$S(n,1)=1$、$S(n,n)=1$ を使う。

$k=2$ の列：
$$S(3,2)=S(2,1)+2S(2,2)=1+2=3$$
$$S(4,2)=S(3,1)+2S(3,2)=1+6=7$$
$$S(5,2)=S(4,1)+2S(4,2)=1+14=15$$

$k=3$ の列：
$$S(4,3)=S(3,2)+3S(3,3)=3+3=6$$
$$S(5,3)=S(4,2)+3S(4,3)=7+18=25$$
$$S(6,3)=S(5,2)+3S(5,3)=15+75=90$$

答え

$$3S(6,3)=3\times 90=270$$

（確認：$S(6,2)=S(5,1)+2S(5,2)=1+30=31$ なので、全体は $S(7,3)=31+270=301$ 通りで、そこから A さんが $1$ 人になる $31$ 通りを除くと $270$ 通りとなり一致する。）

よって $270$ 通り。

7人を区別しない3つの空でないグループに分ける方法の総数は、第2種スターリング数 $S(7,3)=301$ 通りである。

確認: $S(7,3)=\frac{1}{3!}(3^7-3\cdot 2^7+3)=\frac{2187-384+3}{6}=\frac{1806}{6}=301$。

Aさんが1人だけのグループになる分け方は、残り6人を区別しない2つの空でないグループに分ける方法に等しい。これは $S(6,2)=2^5-1=31$ 通りである。

よって求める数は $301-31=270$ 通り。