COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

組分け

組分け

問題≪区別できる玉の組分け≫

 次の各場合に, $r$ 個の玉を $n$ 個の箱に入れる方法の総数を求めよ. ただし, $1$ 個も玉の入らない箱があってもよいとする.
(1)
玉が区別できて, 箱が $\mathrm A_1,$ $\cdots,$ $\mathrm A_n$ と区別されている場合.
(2)
$n = 2$ であり, 玉が区別できて, 箱は区別できない場合.
(3)
$n = 3$ であり, 玉が区別できて, 箱は区別できない場合.
[東京大*], [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)$ 通りが生じる.
(i), (ii) と (1) の結果により \[ 3+3!(N-1) = 3^r\] が成り立つから, \[ N = \frac{3^r+3}{3!} = \frac{3^{r-1}+1}{2}\] である.

別解

(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$ であり, 玉は区別できず, 箱も区別できない場合.
[東京大*]

解答例

(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)$ 通りが生じる.
(i), (ii) から (1) の場合の数は \[ 1+2!(N-1) = r+1\] と表せるので, これを $N$ について解くと \[ N = \frac{r}{2}+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)$ 通りが生じる.
(i)~(iii) から (1) の場合の数は \begin{align*} &1+3\cdot 3k+3!(N-3k-1) \\ &= 6N-9k-5 = 6N-\frac{3r+10}{2} \quad \cdots [2] \end{align*} と表せるので, $[1] = [2]$ を $N$ について解くと \[ N = \frac{r^2+6r+12}{12}\] が得られる.
(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}$ 通りある.
(i), (ii) は排反であるから, ${}_{n+1}\mathrm S_{r+1} = {}_n\mathrm S_r+(r+1){}_n\mathrm S_{r+1}$ が成り立つ.

背景

 互いに区別できる $n$ 個の対象を $r$ 個の組に分ける方法の総数を「第 $2$ 種スターリング数」(Stirling number of the second kind)と呼ぶ. 世界的には $\begin{Bmatrix} n \\ r \end{Bmatrix}$ という記号で表すことが多い.

問題≪ベル数≫

 $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}$ と表される.