第 2 種スターリング数の漸化式と条件つき分割

漸化式 $S (n, k) = S (n - 1, k - 1) + k S (n - 1, k)$ で $S (n, k)$ の表を作れる。「どのブロックも連続する 2 整数 $i, i + 1$ を同時に含まない ${1, \dots, n}$ の $k$ ブロック分割の個数は $S (n - 1, k - 1)$ 」のような帰着を使って、条件つきの分割の個数を求められる（例: $n = 8, k = 3$ で $S (7, 2) = 63$ ）

前提

中学までに習ったことだけで始められます。

説明

有限集合を「区別しない空でない箱（ブロック）」に分ける方法の数を、表を作って順に計算できるようになります。 ${1, 2, \dots, n}$ を、空でない $k$ 個の部分集合で、互いに共通部分がなく、すべて合わせると全体になるものに分けることを $k$ ブロック分割といい、その個数を第 2 種スターリング数 $S (n, k)$ と書きます（ブロックの並び順は区別しません）。漸化式 $S (n, k) = S (n - 1, k - 1) + k S (n - 1, k)$ で表を埋めれば値が求まり、さらに「どのブロックも連続する 2 整数 $i, i + 1$ を同時に含まない」という条件つきの分割も $S (n - 1, k - 1)$ に帰着して数えられます。

なぜそうしてよいのか

【漸化式の理由】 ${1, \dots, n}$ の $k$ ブロック分割を、最後の要素 $n$ の入り方で 2 種類に分けます。(ア) $n$ が 1 人だけのブロック ${n}$ をつくる場合： ${n}$ を取り除くと ${1, \dots, n - 1}$ の $k - 1$ ブロック分割が残り、逆にそこへ ${n}$ を足せば元に戻るので、 $S (n - 1, k - 1)$ 通りです。(イ) $n$ が他の要素と同じブロックにいる場合： $n$ を取り除くと ${1, \dots, n - 1}$ の $k$ ブロック分割が残ります。逆に、その $k$ 個のブロックのどれに $n$ を入れるかで $k$ 通りあり、どれも異なる分割になるので $k S (n - 1, k)$ 通りです。合計して $S (n, k) = S (n - 1, k - 1) + k S (n - 1, k)$ が成り立ちます（ $n \geq 1, k \geq 1$ ）。出発点として、要素が 0 個の集合の 0 ブロック分割（何もしない分け方）を 1 通りと数えて $S (0, 0) = 1$ 、また $n \geq 1$ なら $S (n, 0) = 0$ 、 $k > n$ なら $S (n, k) = 0$ と決めます。

【条件つき分割の帰着】「どのブロックも $i, i + 1$ を同時に含まない」 ${1, \dots, n}$ の $k$ ブロック分割の個数を $T (n, k)$ とします。同じく $n$ の入り方で分けると、(ア) ${n}$ が単独なら残りは条件をみたす $k - 1$ ブロック分割で $T (n - 1, k - 1)$ 通り。(イ) $n$ を条件をみたす $k$ ブロック分割に追加する場合、 $n - 1$ を含むブロックには入れられないので選べるのは $k - 1$ 個で、 $(k - 1) T (n - 1, k)$ 通り。よって $T (n, k) = T (n - 1, k - 1) + (k - 1) T (n - 1, k)$ です。

一方、 $S (n - 1, k - 1)$ に普通の漸化式を使うと $S (n - 1, k - 1) = S (n - 2, k - 2) + (k - 1) S (n - 2, k - 1)$ で、これは $T$ の式で $T (m, j)$ を $S (m - 1, j - 1)$ に置きかえたものとまったく同じ形です。出発点も $T (1, 1) = 1 = S (0, 0)$ 、 $n \geq 2$ のとき $T (n, 1) = 0 = S (n - 1, 0)$ （1 ブロックだと 1 と 2 が同じブロックに入る）と一致するので、 $n$ について順に確かめていけば、すべての $n \geq 1, k \geq 1$ で $T (n, k) = S (n - 1, k - 1)$ となります。

手順

問題の条件を確認する。条件がなければそのまま $S (n, k)$ を求める。「どのブロックも連続する 2 整数 $i, i + 1$ を同時に含まない」なら、求める個数を $S (n - 1, k - 1)$ に置きかえる。
表の端の値を書く： $S (0, 0) = 1$ 、 $n \geq 1$ なら $S (n, 0) = 0$ 、 $k > n$ なら $S (n, k) = 0$ 。とくに $S (n, 1) = 1$ 、 $S (n, n) = 1$ （ $n \geq 1$ ）。
上の行から順に漸化式 $S (n, k) = S (n - 1, k - 1) + k S (n - 1, k)$ で表を埋める。左上の値と、真上の値の $k$ 倍を足す。
必要な $S (n, k)$ （帰着した場合は $S (n - 1, k - 1)$ ）を表から読み取る。

例題

${1, 2, 3, 4, 5, 6, 7}$ を空でない 4 つのブロックに分ける分け方のうち、どのブロックも連続する 2 整数 $i, i + 1$ （ $1 \leq i \leq 6$ ）を同時に含まないものの個数を求めよ。ただしブロックの順序は区別しない。

例題の解答

手順1：連続する 2 整数を同じブロックに含まない ${1, \dots, 7}$ の 4 ブロック分割の個数は $S (7 - 1, 4 - 1) = S (6, 3)$ に等しい。

手順2：端の値 $S (n, 1) = 1$ 、 $S (n, n) = 1$ を置く。

手順3：漸化式 $S (n, k) = S (n - 1, k - 1) + k S (n - 1, k)$ で行ごとに埋める。
$n = 3$ ： $S (3, 2) = S (2, 1) + 2 S (2, 2) = 1 + 2 = 3$ 。
$n = 4$ ： $S (4, 2) = S (3, 1) + 2 S (3, 2) = 1 + 6 = 7$ 、 $S (4, 3) = S (3, 2) + 3 S (3, 3) = 3 + 3 = 6$ 。
$n = 5$ ： $S (5, 2) = 1 + 2 \cdot 7 = 15$ 、 $S (5, 3) = S (4, 2) + 3 S (4, 3) = 7 + 18 = 25$ 。
$n = 6$ ： $S (6, 3) = S (5, 2) + 3 S (5, 3) = 15 + 75 = 90$ 。

手順4：表から $S (6, 3) = 90$ 。よって求める個数は 90 通り。

答え: $90$

よくある誤り

係数をつける項を取り違えて $S (n, k) = k S (n - 1, k - 1) + S (n - 1, k)$ としてしまう誤り。 ${n}$ が単独のときは置き方が 1 通りなので係数は 1、 $n$ を既存の $k$ ブロックに追加するときに $k$ 通りなので、正しくは $S (n, k) = S (n - 1, k - 1) + k S (n - 1, k)$ （例： $S (4, 2) = 1 + 2 \cdot 3 = 7$ ）。
連続整数を含まない条件の帰着先を $S (n - 1, k)$ としてしまう誤り。正しくはブロック数も 1 減って $S (n - 1, k - 1)$ 。たとえば $n = 8, k = 3$ なら $S (7, 3) = 301$ ではなく $S (7, 2) = 63$ 。
ブロックに順序をつけて $k!$ 倍してしまう誤り。 $S (n, k)$ はブロックを区別しない数え方なので、例えば ${1, 2, 3}$ の 2 ブロック分割は ${1} {2, 3}, {2} {1, 3}, {3} {1, 2}$ の $S (3, 2) = 3$ 通りで、 $3 \cdot 2! = 6$ ではない。
条件「 $i, i + 1$ を含まない」を $n$ と $1$ も隣りとみなす（円形の）条件と混同してしまう誤り。 $T (n, k) = S (n - 1, k - 1)$ が成り立つのは $1 \leq i \leq n - 1$ の $i, i + 1$ だけを禁止する場合で、 $n$ と $1$ を同じブロックに入れてもよい。例： $n = 3, k = 2$ では ${1, 3} {2}$ の 1 通りで $S (2, 1) = 1$ と一致する。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

同値関係と集合の分割（大学数学集合と位相）