第 1 種スターリング数

$n$ 文字の置換で巡回がちょうど $k$ 個のものの個数 $[k n]$ を、漸化式 $[k n] = [k - 1 n - 1] + (n - 1) [k n - 1]$ や $x (x + 1) \dots (x + n - 1)$ の $x^{k}$ の係数として求められる

前提

置換の巡回置換分解と位数（大学数学代数学）

この技能までの道筋（22 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

約数の見つけ方（算数整数の性質）
最大公約数と最小公倍数（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
最大公約数と最小公倍数（数学A 整数の性質）
分数のたし算・ひき算（算数計算と数のきまり）
小数の四則計算（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
分数のかけ算・わり算（算数計算と数のきまり）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
乗法公式による展開（中学数学数と式）
因数分解（中学数学数と式）
文字式で表した整数の性質（中学数学数と式）
余りによる整数の分類（数学A 整数の性質）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
合同式（数学A 整数の性質）
群の位数と元の位数（大学数学代数学）
置換の巡回置換分解と位数（大学数学代数学）

説明

第 1 種スターリング数 $[k n]$ は、 $n$ 文字の置換（ $S_{n}$ の元）のうち、互いに素な巡回置換への分解に現れる巡回がちょうど $k$ 個のものの個数です。ここで長さ 1 の巡回（固定点）も 1 個の巡回として数えます。巡回型をすべて列挙しなくても、漸化式で表を作るか、多項式 $x (x + 1) \dots (x + n - 1)$ を展開して $x^{k}$ の係数を読めば求められます。置換の数え上げや、巡回の個数の分布を調べる場面で使います。

なぜそうしてよいのか

$S_{n}$ の置換 $σ$ で巡回が $k$ 個のものを、文字 $n$ の居場所で 2 種類に分けます。(i) $n$ が固定点（長さ 1 の巡回 $(n)$ ）のとき、 $(n)$ を取り除くと残りは $1, \dots, n - 1$ の置換で巡回が $k - 1$ 個です。逆に $n - 1$ 文字で巡回 $k - 1$ 個の置換に $(n)$ を付け加えれば元に戻るので、この種類は $[k - 1 n - 1]$ 個です。(ii) $n$ が長さ 2 以上の巡回に入っているとき、巡回の中から $n$ を抜き取る（ $σ (i) = n$ となる $i$ の行き先を $σ (n)$ につなぎ直す）と、巡回の個数は $k$ のまま変わらない $n - 1$ 文字の置換が得られます。逆に $n - 1$ 文字で巡回 $k$ 個の置換に対して、 $1, \dots, n - 1$ のどれか $i$ を選び、巡回の表記で $i$ のすぐ後ろに $n$ を差し込めば元に戻ります。 $i$ が違えば $σ (i) = n$ となる $i$ が違うので、できる置換も違います。よってこの種類は $(n - 1) [k n - 1]$ 個です。和の法則で合わせると $[k n] = [k - 1 n - 1] + (n - 1) [k n - 1] (n \geq 1)$ が成り立ちます。

初期値は $[0 0] = 1$ （0 文字の置換は何もしない置換 1 個で、巡回は 0 個）、 $n \geq 1$ なら $[0 n] = 0$ 、 $k > n$ なら $[k n] = 0$ です。ここから $[n n] = 1$ （恒等置換）、 $[1 n] = (n - 1)!$ （長さ $n$ の巡回 1 個）も出てきます。

多項式 $P_{n} (x) = x (x + 1) \dots (x + n - 1)$ （ $P_{0} (x) = 1$ ）を考えると $P_{n} (x) = P_{n - 1} (x) (x + n - 1)$ です。右辺の $x^{k}$ の係数は、 $x$ を掛ける側から $P_{n - 1}$ の $x^{k - 1}$ の係数、 $n - 1$ を掛ける側から $(n - 1) \times$ ( $P_{n - 1}$ の $x^{k}$ の係数) が来るので、漸化式とまったく同じ形になります。初期値も一致するので、 $P_{n} (x) = \sum_{k = 0}^{n} [k n] x^{k}$ が成り立ちます。

手順

巡回の数え方を確認する：固定点も長さ 1 の巡回として数え、求めるものが $[k n]$ であることを確かめる。
初期値を置く： $[0 0] = 1$ 、 $n \geq 1$ で $[0 n] = 0$ 、 $k > n$ で $[k n] = 0$ （すぐ使える値として $[n n] = 1$ 、 $[1 n] = (n - 1)!$ ）。
漸化式 $[k n] = [k - 1 n - 1] + (n - 1) [k n - 1]$ で、 $n$ の小さい行から順に表を作る。
別の方法として、 $x (x + 1) \dots (x + n - 1)$ を 1 因子ずつ掛けて展開し、 $x^{k}$ の係数を読む。
検算する：各行の和 $\sum_{k} [k n] = n!$ （多項式に $x = 1$ を代入した値）になっているか確かめる。

例題

5 文字の置換（ $S_{5}$ の元）のうち、互いに素な巡回置換への分解で、長さ 1 の巡回（固定点）も含めて巡回がちょうど 2 個になるものの個数 $[2 5]$ を求めよ。

例題の解答

手順 1：固定点も巡回に数えるので、求めるのは $[2 5]$ である。
手順 2：初期値は $[1 1] = 1$ 、 $[0 n] = 0 (n \geq 1)$ 。
手順 3：漸化式で表を作る。
$n = 2$ ： $[1 2] = 0 + 1 \cdot 1 = 1$ 、 $[2 2] = 1$ 。
$n = 3$ ： $[1 3] = 0 + 2 \cdot 1 = 2$ 、 $[2 3] = 1 + 2 \cdot 1 = 3$ 、 $[3 3] = 1$ 。
$n = 4$ ： $[1 4] = 3 \cdot 2 = 6$ 、 $[2 4] = 2 + 3 \cdot 3 = 11$ 、 $[3 4] = 3 + 3 \cdot 1 = 6$ 、 $[4 4] = 1$ 。
$n = 5$ ： $[2 5] = [1 4] + 4 [2 4] = 6 + 4 \cdot 11 = 50$ 。
手順 4（確認）： $x (x + 1) (x + 2) (x + 3) = x^{4} + 6 x^{3} + 11 x^{2} + 6 x$ に $(x + 4)$ を掛けると、 $x^{2}$ の係数は $6 \cdot 1 + 11 \cdot 4 = 50$ で一致する。
手順 5（検算）： $n = 4$ の行の和は $6 + 11 + 6 + 1 = 24 = 4!$ で正しい。さらに巡回型で数えると、型 $(4, 1)$ が $5 \times 3! = 30$ 個、型 $(3, 2)$ が $(3 5) \times 2 \times 1 = 20$ 個で、合計 $50$ 個と一致する。
よって答えは $50$ 。

答え: $50$

よくある誤り

固定点を巡回に数えない誤り。たとえば $(123)$ を $S_{5}$ の元とみるとき巡回は 1 個ではなく、 $(123) (4) (5)$ で 3 個。正しくは長さ 1 の巡回も数える。
漸化式の係数を $n$ や $k$ にしてしまう誤り（例： $[k n] = [k - 1 n - 1] + k [k n - 1]$ は第 2 種スターリング数の漸化式）。正しくは、 $n$ を差し込む位置が $1, \dots, n - 1$ の後ろの $n - 1$ 通りなので、 $[k n] = [k - 1 n - 1] + (n - 1) [k n - 1]$ 。
多項式を $x (x - 1) \dots (x - n + 1)$ にしてしまう誤り。こちらの係数は $(- 1)^{n - k} [k n]$ と符号が付き、たとえば $x (x - 1) (x - 2) = x^{3} - 3 x^{2} + 2 x$ となる。個数を求めるときは $x (x + 1) \dots (x + n - 1)$ を使う（ $x (x + 1) (x + 2) = x^{3} + 3 x^{2} + 2 x$ ）。
最後の因子を $x + n$ にしてしまう誤り。 $n$ 文字なら因子は $x, x + 1, \dots, x + n - 1$ の $n$ 個で、たとえば $n = 3$ では $x (x + 1) (x + 2)$ であり、 $x (x + 1) (x + 2) (x + 3)$ ではない。

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

入口の問題

この技能を使う問題

難易度 3（期末試験の応用レベル）
集合 ${1, 2, 3, 4, 5, 6, 7}$ の置換（ ${1, \dots, 7}$ から自分自身への全単射） $σ$ を考える。 $σ$ を互いに素な巡回置換の積に分解する。このとき、不動点も長さ $1$ の巡回として数える。分解に現れる巡回の個数がちょうど $3$ であり、しかも $1$ と $2$ が同じ巡回に属するような $σ$ は何個あるか。