数学A / 場合の数

グループ分けの総数(ベル数の漸化式)

実戦編数え上げ漸化式組分け二項係数単元横断

問題

$n$ 人を、区別のないグループにいくつかに分ける方法の総数(各人はちょうど1グループ、空グループは作らない)をベル数 $B_{n}$ とし、 $B_{0} = 1$ とする。(1) $B_{n + 1} = k = 0 \sum n (k n) B_{k}$ を示せ。

(2) $B_{4}$ を求めよ。

ヒントを見る

(1) 特定の1人(例えば最後の人)に注目。その人と同じグループになる残りのメンバーを $n$ 人から選ぶと、残りの人たちの分け方が $B$ で書ける。(2) $B_{0} = 1$ から順に。

解答・解説

方針

(1) $(n + 1)$ 番目の人が属するグループの残りメンバー(残り $n$ 人から選ぶ)の人数で場合分けする。(2) 漸化式を順に計算。

解答

⓪ 発想 — どう考え始めるか。 分け方全体を直接数えるのは難しい。特定の1人に注目して分類する — 数え上げの常套手段だ。

$(n + 1)$ 番目の人が入るグループの「他のメンバー」を、残り $n$ 人から $j$ 人選ぶ( $(j n)$ 通り)。残った $n - j$ 人は自由に分かれる( $B_{n - j}$ 通り)。

$j$ を走らせて足せば $B_{n + 1} = \sum (j n) B_{n - j} = \sum (k n) B_{k}$ ( $k = n - j$ と置き換え)。(2)は漸化式を $B_{1}$ から順に回すだけだ。

① 漸化式を示す。 $(n + 1)$ 番目の人と同じグループになる相手を、残り $n$ 人から $j$ 人選ぶ( $(j n)$ 通り)。この $j + 1$ 人で1グループが決まり、残る $n - j$ 人の分け方は $B_{n - j}$ 通り。よって $B_{n + 1} = j = 0 \sum n (j n) B_{n - j} .$ $k = n - j$ と置き換えると $(j n) = (k n)$ より $B_{n + 1} = k = 0 \sum n (k n) B_{k}$ 。

重要特定の1人の属するグループの残りメンバー(

n

人から選ぶ)で分類 →

B_{n + 1} = \sum_{k = 0}^{n} (k n) B_{k}

② $B_{4}$ を計算する。 $B_{0} = 1$ から順に。 $B_{1} = (0 0) B_{0} = 1,$ $B_{2} = (0 1) B_{0} + (1 1) B_{1} = 1 + 1 = 2,$ $B_{3} = (0 2) B_{0} + (1 2) B_{1} + (2 2) B_{2} = 1 + 2 + 2 = 5,$ $B_{4} = (0 3) B_{0} + (1 3) B_{1} + (2 3) B_{2} + (3 3) B_{3} = 1 + 3 + 6 + 5 = 15.$ よって $B_{4} = 15$ 。

まとめ 特定の1人が属するグループの残りメンバーを選ぶ( $(k n)$ )ことで、 $B_{n + 1} = \sum_{k} (k n) B_{k}$ の漸化式ができる。順に計算して $B_{4} = 15$ 。数え上げと漸化式(ベル数)の融合。

発展 — 一歩先へ。 ベル数 $1, 1, 2, 5, 15, 52, 203, \dots$ は「分け方」の総数として、確率(分割の一様ランダム)、データのクラスタリングの状態数など、応用の広い数列だ。 $B_{n} = \sum_{m} S (n, m)$ (スターリング数の総和)という2階建ての構造、そして本問の漸化式が「指数型母関数 $e^{e^{x} - 1}$ 」という1本の関数に畳み込まれることまで、数え上げの理論の見本市になっている。

答

特定の1人が属するグループの“他のメンバー”の選び方で分類して漸化式。 $B_{1} = 1, B_{2} = 2, B_{3} = 5, B_{4} = 15$ 。

別解

(2)を「グループのサイズの型」で直接数える。 漸化式を使わず、4人の分け方をサイズの型(分割のパターン)で列挙して数えることもできる。

型 ${4}$ (全員1組): $1$ 通り
型 ${3, 1}$ : 1人だけ外す選び方で $(1 4) = 4$ 通り
型 ${2, 2}$ : 2人を選ぶ $(2 4) = 6$ を、2組の入れ替え $2!$ で割って $3$ 通り
型 ${2, 1, 1}$ : ペアを選ぶ $(2 4) = 6$ 通り
型 ${1, 1, 1, 1}$ : $1$ 通り

$B_{4} = 1 + 4 + 3 + 6 + 1 = 15$

漸化式(本解)は $n$ が大きくても機械的に回る量産装置、型別の直接数えは「同サイズのグループは入れ替えても同じ( $2!$ で割る)」という区別の消し方の練習になる。両方で $15$ が出れば、検算も同時に済んでいる。

ポイント

特定の1人が属するグループの残りメンバーで分類する。
$B_{n + 1} = \sum_{k = 0}^{n} (k n) B_{k}$ ( $B_{0} = 1$ )。
順に $B_{1} = 1, B_{2} = 2, B_{3} = 5, B_{4} = 15$ 。

よくある間違い

「特定の1人」を固定せずに漸化式を立てようとして、どのグループ分けを何回数えたか分からなくなる。
型 ${2, 2}$ の数えで $(2 4) = 6$ のまま( $2$ 組の入れ替えで2重に数えている。 $\div 2!$ で3通り)。
グループに区別がない(箱と違う)ことを忘れ、前問(区別できる3箱)と同じ式を書く。