組分け
組分け
問題≪区別できる玉の組分け≫
次の各場合に, $r$ 個の玉を $n$ 個の箱に入れる方法の総数を求めよ.
ただし, $1$ 個も玉の入らない箱があってもよいとする.
- (1)
- 玉が区別できて, 箱が $\mathrm A_1,$ $\cdots,$ $\mathrm A_n$ と区別されている場合.
- (2)
- $n = 2$ であり, 玉が区別できて, 箱は区別できない場合.
- (3)
- $n = 3$ であり, 玉が区別できて, 箱は区別できない場合.
(参考: 1996 東京大, 2019 高知工科大)
解答例
- (1)
- $1$ 個の玉につき $\mathrm A_1,$ $\cdots,$ $\mathrm A_n$ のどの箱に入れるかで $n$ 通りの方法があるから, 求める場合の数は $n^r$ である.
- (2)
- 求める場合の数は, $n = 2$ のとき (1) において箱の区別をなくした場合の数に等しく, $\dfrac{2^r}{2!} = 2^{r-1}$ である.
- (3)
- 求める場合の数を $N$ とおく.
- (i)
- $r$ 個の玉が $1$ つの箱に入る場合は, $1$ 通り.
この状態から箱に $\mathrm A_1,$ $\mathrm A_2,$ $\mathrm A_3$ と名前をつけると, 名前のつけ方は $3$ 通りあるから, (1) の $3$ 通りが生じる. - (ii)
- $r$ 個の玉が複数の箱に入る場合は, $N-1$ 通り.
このとき,玉の入った箱は入っている玉によって区別でき, 空箱は高々 $1$ 個で玉の入った箱と区別できるから, 箱はすべて区別できる. よって, この状態から箱に $\mathrm A_1,$ $\mathrm A_2,$ $\mathrm A_3$ と名前をつけると, 名前のつけ方は $3!$ 通りあるから, (1) の $3!(N-1)$ 通りが生じる.
別解
- (3)
- 区別ができる $r$ 個の玉を区別のできない $3$ つの箱に入れるとき, $r$ 個の玉が $1$ つの箱に入る場合の数を $a_r,$ ちょうど $2$ つの箱の箱に入る場合の数を $b_r,$ ちょうど $3$ つの箱に入る場合の数を $c_r$ とおき, その総数を $N_r$ とおく. このとき, \begin{align*} N_r &= a_r+b_r+c_r, \\ a_{r+1} &= a_r, \\ b_{r+1} &= a_r+2b_r, \\ c_{r+1} &= b_r+3c_r \end{align*} であるから, \begin{align*} N_{r+1} &= a_{r+1}+b_{r+1}+c_{r+1} \\ &= a_r+(a_r+2b_r)+(b_r+3c_r) \\ &= 3(a_r+b_r+c_r)-a_r \\ &= 3N_r-1 \quad [1] \end{align*} が成り立つ. よって, $[1]$ の辺々から $x = 3x-1$ の解 $x = \dfrac{1}{2}$ を引くと \[ N_{r+1}-\frac{1}{2} = 3\left( N_r-\frac{1}{2}\right)\] となる. したがって, $\left\{ N_r-\dfrac{1}{2}\right\}$ は初項 $N_1-\dfrac{1}{2} = \dfrac{1}{2},$ 公比 $3$ の等比数列であるから, \begin{align*} N_r-\frac{1}{2} &= \frac{1}{2}\cdot 3^{r-1} \\ N_r &= \frac{3^{r-1}+1}{2} \end{align*} である.
背景
互いに区別できる $n$ 個の対象を $r$ 個の組に分ける方法の総数を「第 $2$ 種スターリング数」(Stirling number of the second kind)と呼び, ${}_n\mathrm S_r$ で表す.
${}_n\mathrm S_1 = 1$ であり, (2), (3) により ${}_n\mathrm S_1+{}_n\mathrm S_2 = 2^{n-1}, $ ${}_n\mathrm S_1+{}_n\mathrm S_2+{}_n\mathrm S_3 = \dfrac{3^{n-1}+1}{2}$ だから,
\[ {}_n\mathrm S_2 = 2^{n-1}-1, \quad {}_n\mathrm S_3 = \frac{3^{n-1}-2^n+1}{2}\]
である.
問題≪区別できない玉の組分け≫
次の各場合に, $r$ 個の玉を $n$ 個の箱に入れる方法の総数を求めよ.
ただし, $1$ 個も玉の入らない箱があってもよいとする.
- (1)
- 玉は区別できず, 箱が $\mathrm A_1,$ $\cdots,$ $\mathrm A_n$ と区別されている場合.
- (2)
- $n = 2$ であり, 玉は区別できず, 箱も区別できない場合.
- (3)
- $n = 3$ であり, 玉は区別できず, 箱も区別できない場合.
(参考: 1996 東京大)
解答例
- (1)
- $\mathrm A_1,$ $\cdots,$ $\mathrm A_n$ の各箱に入る玉の個数を $x_1,$ $\cdots,$ $x_n$ とおくと, \[ x_1+\cdots +x_n = r, \quad x_1 \geqq 0,\ \cdots,\ x_n \geqq 0\] となり, $x_1,$ $\cdots,$ $x_n$ はそれぞれ $r$ 個の〇と $n-1$ 本の|の順列において|で仕切られた〇の個数に対応するから, 求める場合の数は \[ {}_{n+r-1}\mathrm C_{n-1} = {}_{n+r-1}\mathrm C_r = \frac{(n+r-1)!}{(n-1)!r!}\] である.
- (2)
- $n = 2$ のとき, (1) の場合の数は
\[ {}_{2-1+r}\mathrm C_{2-1} = r+1\]
である.
求める場合の数を $N$ とおく.
- (I)
- $r$ が奇数の場合. $2$ つの箱に入る玉の個数は異なるので, この状態から箱に $\mathrm A_1,$ $\mathrm A_2$ と名前をつける方法は $2!$ 通りある. よって, (1) の場合の数について \[ 2!N = r+1\] が成り立つから, \[ N = \frac{r+1}{2}\] である.
- (II)
- $r = 2k$ ($k$: 正の整数)の場合.
- (i)
- $2$ つの箱に入る玉の個数が等しい場合, 玉の個数の組合せは $\{ k,k\}$ の $1$ 通り. この状態から箱に $\mathrm A_1,$ $\mathrm A_2$ と名前をつけると, 名前のつけ方は $1$ 通りあるから, (1) の $1$ 通りが生じる.
- (ii)
- $2$ つの箱に入る玉の個数が異なる場合, 玉の個数の組合せは $N-1$ 通り. この状態から箱に $\mathrm A_1,$ $\mathrm A_2$ と名前をつけると, 名前のつけ方は $2!$ 通りあるから, (1) の $2!(N-1)$ 通りが生じる.
- (3)
- $n = 3$ のとき, (1) の場合の数は
\[ {}_{3-1+r}\mathrm C_{3-1} = \frac{(r+2)(r+1)}{2} \quad \cdots [1]\]
である.
求める場合の数を $N$ とおく.
- (I)
- $r = 6k$ ($k$: 正の整数)の場合.
- (i)
- 各箱に入る玉の個数がすべて等しい場合, 玉の個数の組合せは $\{ 2k,2k,2k\}$ の $1$ 通り. この状態から箱に A, B, C と名前をつけると, 名前のつけ方は $1$ 通りあるから, (1) の $1$ 通りが生じる.
- (ii)
- 各箱に入る玉の個数が $2$ 箱だけ等しい場合, 玉の個数の組合せは $\{ 0,0,6k\},$ $\cdots,$ $\{ 3k,3k,0\}$ から (i) の場合を除いた $3k$ 通り. この状態から箱に A, B, C と名前をつけると, 名前のつけ方は $\dfrac{3!}{2!} = 3$ 通りあるから, (1) の $3\cdot 3k$ 通りが生じる.
- (iii)
- 各箱に入る玉の個数がすべて異なる場合は, $N-3k-1$ 通り. この状態から箱に A, B, C と名前をつけると, 名前のつけ方は $3!$ 通りあるから, (1) の $3!(N-3k-1)$ 通りが生じる.
- (II)
- $r = 6k+1$ ($k$: 非負整数)の場合. (I) と同様に考えて (1) の場合の数は \begin{align*} &0+3(3k+1)+3!(N-3k-1) \\ &= 6N-9k-3 = 6N-\frac{3(r+1)}{2} \end{align*} と表せるから, \[ N = \frac{(r+1)(r+5)}{12}\] である.
- (III)
- $r = 6k+2$ ($k$: 非負整数)の場合. (I) と同様に考えて (1) の場合の数は \begin{align*} &0+3(3k+2)+3!(N-3k-2) \\ &= 6N-9k-6 = 6N-\frac{3(r+2)}{2} \end{align*} と表せるから, \[ N = \frac{(r+2)(r+4)}{12}\] である.
- (IV)
- $r = 6k+3$ ($k$: 非負整数)の場合. (I) と同様に考えて (1) の場合の数は \begin{align*} &1+3(3k+1)+3!(N-3k-2) \\ &= 6N-9k-8 = 6N-\frac{3r+7}{2} \end{align*} と表せるから, \[ N = \frac{(r+3)^2}{12}\] である.
- (V)
- $r = 6k+4$ ($k$: 非負整数)の場合. (I) と同様に考えて (1) の場合の数は \begin{align*} &0+3(3k+3)+3!(N-3k-3) \\ &= 6N-9k-9 = 6N-\frac{3(r+2)}{2} \end{align*} と表せるから, \[ N = \frac{(r+2)(r+4)}{12}\] である.
- (VI)
- $r = 6k+5$ ($k$: 非負整数)の場合. (I) と同様に考えて (1) の場合の数は \begin{align*} &0+3(3k+3)+3!(N-3k-3) \\ &= 6N-9k-9 = 6N-\frac{3(r+1)}{2} \end{align*} と表せるから, \[ N = \frac{(r+1)(r+5)}{12}\] である.
背景
(1) のように $n$ 種類のものから重複を許して $r$ 個をとる選び方を重複組合せ(combination with repetition)と呼び, その総数を ${}_n\mathrm H_r$ で表す.
問題≪スターリング数≫
$n \geqq r$ のとき, $n$ 人を $r$ 個の組に分ける方法の総数を ${}_n\mathrm S_r$ で表す.
$n > r$ のとき, ${}_{n+1}\mathrm S_{r+1} = {}_n\mathrm S_r+(r+1){}_n\mathrm S_{r+1}$ が成り立つことを示せ.
解答例
特定の人物 A を含む $n+1$ 人を $r+1$ 個の組に分ける方法を考える.
- (i)
- A が単独のとき. A 以外の $n$ 人を $r$ 個の組に分ける ${}_n\mathrm S_r$ 通りある.
- (ii)
- A が単独でないとき. まず A 以外の $n$ 人を $r+1$ 個の組に分けてから A がどの組に加わるかを考えると, $(r+1){}_n\mathrm S_{r+1}$ 通りある.
背景
互いに区別できる $n$ 個の対象を $r$ 個の組に分ける方法の総数を「第 $2$ 種スターリング数」(Stirling number of the second kind)と呼ぶ.
世界的には $\begin{Bmatrix} n \\ r \end{Bmatrix}$ という記号で表すことが多い.
初めの方の「第 $2$ 種スターリング数」を求めると, 次の表のようになる.
$n$\$r$ | $\,1\,$ | $\,2\,$ | $\,3\,$ | $\,4\,$ | $\,5\,$ |
$1$ | $1$ | ||||
$2$ | $1$ | $1$ | |||
$3$ | $1$ | $3$ | $1$ | ||
$4$ | $1$ | $7$ | $6$ | $1$ | |
$5$ | $1$ | $15$ | $25$ | $10$ | $1$ |
問題≪ベル数≫
$n$ 人を $1$ 人以上の組に分ける方法の総数を $B(n)$ で表し, $B(0) = 1$ と定める.
$B(n+1) = \sum\limits_{k = 0}^n{}_n\mathrm C_kB(k)$ が成り立つことを示せ.
解答例
特定の人物 A を含む $n+1$ 人の組分けを考える.
$0 \leqq k \leqq n$ なる整数 $k$ について A が $k+1$ 人の組に分けられるとき,
A と同じ組に属する人の選び方は A を除く $n$ 人から $k$ 人を選ぶ組合せの ${}_n\mathrm C_k$ 通りあり,
その各場合について残りの $(n+1)-(k+1) = n-k$ 人を組に分ける $B(n-k)$ 通りがあるから,
このような組分けの方法は ${}_n\mathrm C_kB(n-k)$ 通りある.
ゆえに,
\begin{align*}
B(n+1) &= \sum\limits_{k = 0}^n{}_n\mathrm C_kB(n-k) = \sum\limits_{k = 0}^n{}_n\mathrm C_{n-k}B(n-k) \\
&= \sum\limits_{k = 0}^n{}_n\mathrm C_kB(k)
\end{align*}
が成り立つ.
背景
互いに区別できる $n$ 個の対象を $1$ 個以上の対象からなる組に分ける方法の総数を「ベル数」(Bell number)と呼び, $B(n)$ で表す.
「ベル数」は「第 $2$ 種スターリング数」を使って $B(n) = \sum\limits_{k = 1}^n\begin{Bmatrix} n \\ k \end{Bmatrix}$ と表される.
初めの方の「ベル数」を求めると,
\begin{align*}
B(1) &= 1, & B(2) &= 2, & B(3) &= 5, \\
B(4) &= 15, & B(5) &= 52, & &\cdots
\end{align*}
のようになる.