スターリング数

スターリング数（スターリングすう、テンプレート:Lang-en-short）は、上昇階乗冪 (テンプレート:En) や下降階乗冪 (テンプレート:En) を数値の冪乗と関係づけるための級数の展開係数として、イギリスの数学者テンプレート:仮リンクが1730年に彼の著書 Methodus Differentialis で導入した数^[1]である。スターリング数は第1種スターリング数と、第2種スターリング数に分類される。第1種スターリング数はべき乗から階乗への変換に、第2種スターリング数は階乗からべき乗への変換に現れる。また、スターリング数は組合せ数学において意味をもった数値を与える。

第1種スターリング数

第1種スターリング数 (en:Stirling numbers of the first kind) $[\binom{n}{k}]$ は、上昇階乗冪 $x^{\overline{n}} \equiv x (x + 1) (x + 2) \dots (x + n - 1)$ を $x$ のべき級数：

x^{\overline{n}} = \sum_{k = 0}^{n} [\binom{n}{k}] x^{k}

で表現したときの展開係数として定義される。この定義では $0 \leq k \leq n$ である。また、便宜上 $[\binom{0}{0}] = 1$ と定義する。第1種スターリング数は、

[\binom{n}{k}] = [\binom{n - 1}{k - 1}] + (n - 1) [\binom{n - 1}{k}]

なる漸化式で計算できる。この漸化式は、べき級数の展開係数としての定義から導出できる。第1種スターリング数の中で、簡単な数式で書ける成分として、

[\binom{n}{0}] = 0, [\binom{n}{1}] = (n - 1)!, [\binom{n}{n - 1}] = (\binom{n}{2}), [\binom{n}{n}] = 1

が挙げられる。なお、 $(\binom{n}{2})$ は二項係数（二項定理を参照）である。これらは上記の漸化式を用いれば証明できる。特に、第1の関係式は、 $0^{\overline{n}} = 0$ であることから導くこともできる。上に示した漸化式に従い、第1種スターリング数は下表のように計算される。なお、表中の空欄に位置する数値はゼロであると解釈する。

n ＼ k	0	1	2	3	4	5	6	7
0	1
1	0	1
2	0	1	1
3	0	2	3	1
4	0	6	11	6	1
5	0	24	50	35	10	1
6	0	120	274	225	85	15	1
7	0	720	1764	1624	735	175	21	1

下降階乗冪 $x^{\underline{n}} \equiv x (x - 1) (x - 2) \dots (x - n + 1)$ も第1種スターリング数を含む展開係数を伴い、 $x$ のべき級数で表現できる。具体的には、

x^{\underline{n}} = \sum_{k = 0}^{n} (- 1)^{n + k} [\binom{n}{k}] x^{k}

と書けるので、展開係数は第1種スターリング数に符号補正 $(- 1)^{n + k}$ を施した値である。この展開式は、

\begin{matrix} x^{\underline{n}} & = x (x - 1) (x - 2) \dots (x - n + 1) \\ = (- 1)^{n} \cdot (- x) (- x + 1) (- x + 2) \dots (- x + n - 1) \\ = (- 1)^{n} (- x)^{\overline{n}} \end{matrix}

であることに注意すれば容易に証明できる。

第1種スターリング数の性質

\begin{matrix} \sum_{k = 0}^{n} [\binom{n}{k}] = n!, \\ \sum_{k = 0}^{n} 2^{k} [\binom{n}{k}] = (n + 1)!, \\ \sum_{k = 0}^{n} (- 1)^{k} [\binom{n}{k}] = 0 (n \geq 2) \end{matrix}

第1の関係式は、 $1^{\overline{n}} = n!$ から導かれる。第2の関係式は $2^{\overline{n}} = (n + 1)!$ から導かれる。第3の関係式は $n \geq 2$ に関して、 $(- 1)^{\overline{n}} = 0$ であることから導かれる。

第1種スターリング数はベルヌーイ数 $B_{k}$ と次のような関係がある。

\begin{matrix} \frac{1}{m!} \sum_{k = 0}^{m} [\binom{m + 1}{k + 1}] B_{k} = \frac{1}{m + 1}, \\ \frac{1}{(m - 1)!} \sum_{k = 0}^{m} [\binom{m}{k}] B_{k} = - \frac{1}{m + 1} (m \geq 1) . \end{matrix}

第1の関係式は、上昇階乗冪の和の公式：

\sum_{k = 0}^{n - 1} (k + 1)^{\overline{m}} = \frac{n^{\overline{m + 1}}}{m + 1}

から導くことができる。第2の関係式は、第1の関係式に第1種スターリング数の漸化式を適用すれば導かれる。

組み合わせ数学における意味

第1種スターリング数 $[\binom{n}{k}]$ は、組合せ数学において、 $n$ 個の要素を $k$ 個の巡回列に分割する組み合わせの数を与える。巡回列は山手線の駅のように繰り返される要素を示したデータ列である。ここでは、巡回列を $(0, 2, 1, 3)$ のように書こう。この場合、0, 2, 1, 3の順に数値が繰り返される場合を意味する。巡回列の場合、順列ではあるが $(0, 2, 1, 3)$ と $(2, 1, 3, 0)$ のように要素を巡回置換した巡回列どうしは同一とみなす。したがって、 $n$ 個の要素で構成される巡回列の組み合わせは $(n - 1)!$ 通りである。また、 $(1)$ は1個の要素で構成される巡回列であると考える。

例として4個の要素を巡回列2個に分割する組み合わせを考えようそのような分割においては、構成要素が1個と3個の巡回列に分割する組み合わせと、構成要素が2個と2個の巡回列に分割する組み合わせがある。前者の分割法では、4個の要素から、単独で巡回列をなす要素1個を選び、残りの3個の要素で巡回列を作る組み合わせを考えればよい。要素4個から1個を選ぶ組み合わせは4通りであり、3個の要素から巡回列を作る組み合わせは2通りである。したがって、前者の分割法による組み合わせは全部で8通りとなる。後者については、4個の要素から巡回列をなす2個を選び、それぞれ2個の巡回列の組み合わせを考えればよい。要素4個から2個を選ぶのは6通りの組み合わせがあり、2個の要素が巡回列は1通りしかない。しかし、得られる2個の巡回列は同一構造の巡回列なので、6通りの組み合わせからその自由度を補正する必要がある。つまり、2分の1するということであり、後者の分割法による組み合わせは3通りである。つまり、4個の要素を巡回列2個に分割する組み合わせは全部で11通りとなる。この数値は $[\binom{4}{2}]$ と一致する。そのような組み合わせをすべて列挙すると以下のようになる。

\begin{matrix} [(0), (1, 2, 3)], & [(0), (1, 3, 2)], & [(1), (0, 2, 3)], & [(1), (0, 3, 2)] \\ [(2), (0, 1, 3)], & [(2), (0, 3, 1)], & [(3), (0, 1, 2)], & [(3), (0, 2, 1)] \\ [(0, 1), (2, 3)], & [(0, 2), (1, 3)], & [(0, 3), (1, 2)] \end{matrix}

上で説明した直接的な順列の作り方のほかに、4個の要素から巡回列2個を作る方法として次の手順を考える。手順1として、3個の要素から巡回列1個を作り、4番目の要素を単独要素の巡回列として追加する。手順2として、3個の要素から巡回列2個を作り、4番目の要素を既に作られた巡回列に追加する。手順1では、3個の要素から巡回列を作る組み合わせとして2通りが可能である。手順2では、3個の要素から巡回列2個を作る組み合わせが3通りある。さらに、4番目の要素を既存の巡回列に挿入する組み合わせは3通りずつあるので、手順2による組み合わせは9通りとなる。よって、手順1と手順2による組み合わせの合計として11通りになる。

この考え方を一般化し、 $n$ 個の要素から巡回列 $k$ 個を作るには、手順1として、 $n - 1$ 個の要素から巡回列 $k - 1$ 個を作った後、 $k$ 番目の巡回列として $n$ 番目の要素を単独で追加する。その組み合わせの数は、 $n - 1$ 個の要素から巡回列 $k - 1$ 個を作る組み合わせの数に等しい。手順2として、 $n - 1$ 個の要素から巡回列 $k$ 個を作った後、 $n$ 番目の要素を既存の巡回列に挿入する。その組み合わせの数は、 $n - 1$ 個の要素から巡回列 $k$ 個を作る組み合わせの数を $n - 1$ 倍した値となる。手順1と手順2の組み合わせの和であることを考えると、 $n$ 個の要素から巡回列 $k$ 個を作る組み合わせの数は第1スターリング数の漸化式で与えられることがわかる。したがって、その組み合わせの数は第1スターリング数 $[\binom{n}{k}]$ に等しい。

第2種スターリング数

第2種スターリング数 (en:Stirling numbers of the second kind) ${\binom{n}{k}}$ は、 $x^{n}$ を下降階乗冪 $x^{\underline{k}} \equiv x (x - 1) (x - 2) \dots (x - k + 1)$ の級数：

x^{n} = \sum_{k = 0}^{n} {\binom{n}{k}} x^{\underline{k}}

で展開したときの展開係数として定義される。この定義では、 $0 \leq k \leq n$ である。便宜上、 ${\binom{0}{0}} = 1$ と定義する。第2種スターリング数は

{\binom{n}{k}} = {\binom{n - 1}{k - 1}} + k {\binom{n - 1}{k}}

なる漸化式で計算できる。この漸化式は、上記の級数展開による定義から導出できる。その漸化式に従うと、第2種スターリング数は下表のよう計算される。

n ＼ k	0	1	2	3	4	5	6	7
0	1
1	0	1
2	0	1	1
3	0	1	3	1
4	0	1	7	6	1
5	0	1	15	25	10	1
6	0	1	31	90	65	15	1
7	0	1	63	301	350	140	21	1

第2種スターリング数 ${\binom{n}{k}}$ は、第1種スターリング数に符号補正を施した $(- 1)^{n + k} [\binom{n}{k}]$ に対して逆行列の関係、すなわち、

\sum_{k = 0}^{N} (- 1)^{n + k} [\binom{n}{k}] {\binom{k}{m}} = δ_{n m}

の関係を満たす。ただし、 $N \geq n, m$ とする。また、 $δ_{n m}$ はクロネッカーのデルタである。この関係は、 $x^{n}$ を下降階乗冪 $x^{\underline{k}}$ で展開した数式に対し、 $x^{\underline{k}}$ を $x$ のべき級数で展開すれば導出できる。べき乗 $x^{n}$ は上昇階乗冪 $x^{\overline{k}}$ で展開した場合も、第2種スターリング数を含む展開係数を伴う。その展開した結果は、

x^{n} = \sum_{k}^{n} (- 1)^{n + k} {\binom{n}{k}} x^{\overline{k}}

となり、展開係数は第2種スターリング数に符号補正 $(- 1)^{n + k}$ を施した値である。この展開式は、 $x^{\underline{k}} = (- 1)^{k} (- x)^{\overline{k}}$ であることに注意すれば導出できる。

第2種スターリング数の性質

\begin{matrix} \sum_{k = 1}^{n} (- 1)^{k} (k - 1)! {\binom{n}{k}} = 0 (n \geq 2), \\ \sum_{k = 0}^{n} (- 1)^{n + k} k! {\binom{n}{k}} = 1, \\ \sum_{k = 0}^{n} (- 1)^{n + k} (k + 1)! {\binom{n}{k}} = 2^{n} \end{matrix}

第1の関係式は第2種スターリング数の漸化式から導出できる。第2の関係式は、 $(- 1)^{\underline{k}} = (- 1)^{k} k!$ であることから導出できる。第3の関係式は $(- 2)^{\underline{k}} = (- 1)^{k} (k + 1)!$ から導出できる。

第2種スターリング数もベルヌーイ数との関係を示すことができる。

\begin{matrix} B_{k - 1} = \sum_{m = 1}^{k} (- 1)^{k + m} \frac{(m - 1)!}{m} {\binom{k}{m}}, \\ B_{k} = \sum_{m = 0}^{k} (- 1)^{m} \frac{m!}{m + 1} {\binom{k}{m}} \end{matrix}

第1の関係式は、第1種スターリング数とベルヌーイ数の関係式から導出できる。第2の関係式は、第1の関係式に第2種スターリング数の漸化式を適用すれば導出できる。さらに、第2種スターリング数は公式:

{\binom{n}{k}} = \frac{1}{k!} \sum_{m = 1}^{k} (- 1)^{k - m} (\binom{k}{m}) m^{n}

によって一般項が計算できる。しかし、この公式も総和記号を含んでいるため、漸化式よりも便利な公式とは言いがたいが、この公式をベルヌーイ数との関係式（第2の関係式）に代入すればベルヌーイ数の一般項を得ることができる。

組み合わせ数学における意味

第2種スターリング数 ${\binom{n}{k}}$ は、組合せ数学において、番号づけされた $n$ 個の要素をグループ $k$ 個に分割する組み合わせの数を与える。分割する要素は番号付けされているので個別に区別できるが、グループは順序を特に区別しないものとする。選択された要素を $(0, 2, 3)$ と書いた場合、 $(0, 3, 2)$ のように要素を置換した列も同一であるとみなす。分割されたグループに含まれる要素の数は均等である必要はなく、1個の要素しか含まないグループがあってもよいとする。要素4個をグループ2個に分割するには、要素が1個と3個のグループに分割する場合と、要素が2個と2個のグループに分割する組み合わせが挙げられる。前者の分割法では、要素4個から単独グループをなす要素1個を選ぶ組み合わせ、すなわち、4通りだけが存在する。後者の分割法では、要素4個から一方のグループを構成する2個を選ぶ組み合わせを考えればよい。その組み合わせは6通りあるのだが、分割される双方のグループが要素2個で構成されることから、グループ間に対称性がある。その対称性から2の自由度がある。その自由度を補正すると、後者の分割法は3通りの組み合わせがあることになる。したがって、要素 0, 1, 2, 3 をグループ2個に分割する組み合わせは、全部で以下の7通りがある。

\begin{matrix} [(0), (1, 2, 3)], & [(1), (0, 2, 3)], & [(2), (0, 1, 3)], & [(3), (0, 1, 2)], \\ [(0, 1), (2, 3)], & [(0, 2), (1, 3)], & [(0, 3), (1, 2)] \end{matrix}

上で列挙した要素4個をグループ2個に分割する組み合わせは、次のように構成することもできる。手順1として、要素3個をグループ1個に分割し、4番目の要素を第2のグループとして単独で追加する。手順2として、要素3個をグループ2個に分割し、4番目の要素をどちらかのグループに挿入する。手順1で構成される組み合わせは、要素3個をグループ1個に分割する組み合わせの数:1通りに等しい。手順2で構成される組み合わせは、要素3個をグループ2個に分割する組み合わせの数:3通りに対して、4番目の要素を2つのグループのどちらかに挿入する組み合わせ（2 通り）があるので、全部で6通りである。手順1と手順2による組み合わせの和は7通りとなり、上で列挙した組み合わせの数と一致する。

これを一般化して、要素 $n$ 個をグループ $k$ 個に分割するには、次の2つの手順で組み合わせを作ればよい。手順1として、要素 $n - 1$ 個をグループ $k - 1$ 個に分割し、 $n$ 番目の要素を $k$ 番目のグループとして単独で追加すればよい。手順2として、要素 $n - 1$ 個をグループ $k$ 個に分割し、 $n$ 番目の要素を $k$ 個のグループのどれかに挿入する。手順1で構成される組み合わせの数は、要素 $n - 1$ 個をグループ $k - 1$ 個に分割する組み合わせの数に等しい。手順2で構成される組み合わせの数は、要素 $n - 1$ 個をグループ $k$ に分割する組み合わせの数の $k$ 倍に等しい。したがって、手順1と手順2で構成される組み合わせの和として、求める組み合わせの数は第2種スターリング数の漸化式で与えられる。要素 $n$ 個をグループ $k$ 個に分割する組み合わせは、第2種スターリング数 ${\binom{n}{k}}$ で与えられる。

脚注

テンプレート:脚注ヘルプテンプレート:Reflist

外部リンク

テンプレート:高校数学の美しい物語

テンプレート:二項演算

↑ Charalambos A., Charalambides, "Combinatorial Methods in Discrete Distributions," John Wiley & Sons, Inc., p.73, 2005.

[1] Charalambos A., Charalambides, "Combinatorial Methods in Discrete Distributions," John Wiley & Sons, Inc., p.73, 2005.

[1]

スターリング数

目次

第1種スターリング数

第1種スターリング数の性質

組み合わせ数学における意味

第2種スターリング数

第2種スターリング数の性質

組み合わせ数学における意味

脚注

関連項目

外部リンク

ナビゲーションメニュー

スターリング数

第1種スターリング数

第1種スターリング数の性質

組み合わせ数学における意味

第2種スターリング数

第2種スターリング数の性質

組み合わせ数学における意味

脚注

関連項目

外部リンク

ナビゲーション メニュー

検索

ナビゲーションメニュー