スターリング数

スターリング数（スターリングすう、英: Stirling number）は、上昇階乗冪 (rising factorial) や 下降階乗冪 (falling factorial) を数値の冪乗と関係づけるための級数の展開係数として、イギリスの数学者ジェームズ・スターリングが1730年に彼の著書 Methodus Differentialis で導入した数である。スターリング数は第1種スターリング数と、第2種スターリング数に分類される。 第1種スターリング数はべき乗から階乗への変換に、第2種スターリング数は階乗からべき乗への変換に現れる。また、スターリング数は組合せ数学において意味をもった数値を与える。

第1種スターリング数

第1種スターリング数 (Stirling number of the first kind) [math][{\textstyle{n\atop k}}][/math] は、上昇階乗冪 [math]x^{\overline{n}}\equiv x(x + 1)(x + 2)\cdots(x + n - 1)[/math] を [math]x[/math] のべき級数:

[math] x^{\overline{n}} = \sum_{k=0}^{n} \left[{n\atop k}\right]\,x^k [/math]

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

[math] \left[{n\atop k}\right] = \left[{n-1\atop k-1}\right] + (n - 1)\,\left[{n-1\atop k}\right] [/math]

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

[math] \left[{n\atop 0}\right] = 0,\quad \left[{n\atop 1}\right] = (n-1)!,\quad \left[{n\atop n-1}\right] = \left({n \atop 2}\right),\quad \left[{n\atop n}\right] = 1 [/math]

が挙げられる。なお、[math]({\textstyle{n\atop2}})[/math]は二項係数（二項定理 参照）である。これらは上記の漸化式を用いれば証明できる。特に、第1の関係式は、[math]0^{\overline{n}}=0[/math] であることから導くこともできる。上に示した漸化式にしたがい、第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

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

[math] x^{\underline{n}} = \sum_{k=0}^{n} (-1)^{n+k}\left[ {n\atop k}\right]\,x^k [/math]

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

[math] \begin{align} x^{\underline{n}} & = x\,(x-1)(x-2)\cdots(x-n+1) \\ & = (-1)^n\cdot(-x)(-x+1)(-x+2)\cdots(-x+n-1) \\ & = (-1)^n\,(-x)^{\overline{n}} \end{align} [/math]

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

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

[math] \begin{align} & \sum_{k=0}^{n} \left[{n\atop k}\right] = n!,\\ & \sum_{k=0}^{n} 2^k\left[{n\atop k}\right] = (n+1)!,\\ & \sum_{k=0}^{n} (-1)^k\left[{n\atop k}\right] = 0\quad(n\geq2) \end{align} [/math]

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

第1種スターリング数はベルヌーイ数 [math]B_k[/math] と次のような関係がある。

[math] \begin{align} & \frac{1}{m!} \sum_{k=0}^m \left[{m+1\atop k+1}\right]\,B_k = \frac{1}{m+1},\\ & \frac{1}{(m-1)!} \sum_{k=0}^m \left[{m\atop k}\right]\,B_k = -\frac{1}{m+1}\quad(m\geq1). \end{align} [/math]

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

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

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

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

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

[math] \begin{array}{llll} {} [(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{array} [/math]

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

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

第2種スターリング数

第2種スターリング数 (Stirling number of the second kind) [math]\{{\textstyle{n\atop k}}\}[/math] は、[math]x^n[/math] を下降階乗冪 [math]x^{\underline{k}}\equiv x\,(x-1)(x-2)\cdots(x-k+1)[/math] の級数:

[math] x^{n} = \sum_{k=0}^{n} \left\{{n\atop k}\right\}\,x^{\underline{k}} [/math]

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

[math] \left\{{n\atop k}\right\} = \left\{{n-1\atop k-1}\right\} + k\,\left\{{n-1\atop k}\right\} [/math]

なる漸化式で計算できる。この漸化式は、上記の級数展開による定義から導出できる。その漸化式にしたがうと、第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種スターリング数 [math]\{{\textstyle{n\atop k}}\}[/math] は、第1種スターリング数に符号補正を施した [math](-1)^{n+k}[{\textstyle{n\atop k}}][/math] に対して逆行列の関係、すなわち、

[math] \sum_{k=0}^{N} (-1)^{n+k}\left[{n\atop k}\right]\,\left\{ {k\atop m}\right\} = \delta_{nm} [/math]

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

[math] x^n = \sum_{k}^{n}(-1)^{n+k}\left\{{n\atop k}\right\}\,x^{\overline{k}} [/math]

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

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

[math] \begin{align} & \sum_{k=1}^n(-1)^k(k-1)!\left\{{n\atop k}\right\}=0\quad\quad(n\geq2),\\ & \sum_{k=0}^n(-1)^{n+k} k!\left\{{n\atop k}\right\}=1,\\ & \sum_{k=0}^n(-1)^{n+k} (k+1)!\left\{{n\atop k}\right\}=2^n \end{align} [/math]

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

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

[math] \begin{align} & B_{k-1} = \sum_{m=1}^k (-1)^{k+m}\frac{(m-1)!}{m} \left\{{k\atop m}\right\},\\ & B_{k} = \sum_{m=0}^k (-1)^m \frac{m!}{m+1} \left\{{k\atop m}\right\} \end{align} [/math]

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

[math] \left\{{n\atop k}\right\} = \frac{1}{k!} \sum_{m=1}^k (-1)^{k-m} \left({k\atop m}\right)m^n [/math]

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

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

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

[math] \begin{array}{llll} {} [(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{array} [/math]

上で列挙した要素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通りとなり、上で列挙した組み合わせの数と一致する。

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

関連項目

• 集合の分割
• ベル数
• 階乗冪