スターリング数

スターリング数（スターリングすう、英: Stirling number）は、上昇階乗冪 (rising factorial) や下降階乗冪 (falling factorial) を数値の冪乗と関係づけるための級数の展開係数として、イギリスの数学者ジェームズ・スターリング（英語版）が1730年に彼の著書 Methodus Differentialis で導入した数である。スターリング数は第1種スターリング数と、第2種スターリング数に分類される。第1種スターリング数はべき乗から階乗への変換に、第2種スターリング数は階乗からべき乗への変換に現れる。また、スターリング数は組合せ数学において意味をもった数値を与える。 第1種スターリング数 (en:Stirling numbers of the first kind) [ n k ] {\displaystyle [{\textstyle {n \atop k}}]} は、上昇階乗冪 x n ¯ ≡ x ( x + 1 ) ( x + 2 ) ⋯ ( x + n − 1 ) {\displaystyle x^{\overline {n}}\equiv x(x+1)(x+2)\cdots (x+n-1)} を x {\displaystyle x} のべき級数： x n ¯ = ∑ k = 0 n [ n k ] x k {\displaystyle x^{\overline {n}}=\textstyle \sum \limits _{k=0}^{n}\displaystyle \left[{n \atop k}\right]\,x^{k}} で表現したときの展開係数として定義される。この定義では 0 ≤ k ≤ n {\displaystyle 0\leq k\leq n} である。また、便宜上 [ 0 0 ] = 1 {\displaystyle [{\textstyle {0 \atop 0}}]=1} と定義する。第1種スターリング数は、 [ n k ] = [ n − 1 k − 1 ] + ( n − 1 ) [ n − 1 k ] {\displaystyle \left[{n \atop k}\right]=\left[{n-1 \atop k-1}\right]+(n-1)\,\left[{n-1 \atop k}\right]} なる漸化式で計算できる。この漸化式は、べき級数の展開係数としての定義から導出できる。第1種スターリング数の中で、簡単な数式で書ける成分として、 [ n 0 ] = 0 , [ n 1 ] = ( n − 1 ) ! , [ n n − 1 ] = ( n 2 ) , [ n n ] = 1 {\displaystyle \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} が挙げられる。なお、 ( n 2 ) {\displaystyle ({\textstyle {n \atop 2}})} は二項係数（二項定理を参照）である。これらは上記の漸化式を用いれば証明できる。特に、第1の関係式は、 0 n ¯ = 0 {\displaystyle 0^{\overline {n}}=0} であることから導くこともできる。上に示した漸化式に従い、第1種スターリング数は下表のように計算される。なお、表中の空欄に位置する数値はゼロであると解釈する。 下降階乗冪 x n _ ≡ x ( x − 1 ) ( x − 2 ) ⋯ ( x − n + 1 ) {\displaystyle x^{\underline {n}}\equiv x\,(x-1)(x-2)\cdots (x-n+1)} も第1種スターリング数を含む展開係数を伴い、 x {\displaystyle x} のべき級数で表現できる。具体的には、 x n _ = ∑ k = 0 n ( − 1 ) n + k [ n k ] x k {\displaystyle x^{\underline {n}}=\textstyle \sum \limits _{k=0}^{n}(-1)^{n+k}\displaystyle \left[{n \atop k}\right]\,x^{k}} と書けるので、展開係数は第1種スターリング数に符号補正 ( − 1 ) n + k {\displaystyle (-1)^{n+k}} を施した値である。この展開式は、 x n _ = x ( x − 1 ) ( x − 2 ) ⋯ ( x − n + 1 ) = ( − 1 ) n ⋅ ( − x ) ( − x + 1 ) ( − x + 2 ) ⋯ ( − x + n − 1 ) = ( − 1 ) n ( − x ) n ¯ {\displaystyle {\begin{aligned}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{aligned}}} であることに注意すれば容易に証明できる。 ∑ k = 0 n [ n k ] = n ! , ∑ k = 0 n 2 k [ n k ] = ( n + 1 ) ! , ∑ k = 0 n ( − 1 ) k [ n k ] = 0 ( n ≥ 2 ) {\displaystyle {\begin{aligned}&\textstyle \sum \limits _{k=0}^{n}\displaystyle \left[{n \atop k}\right]=n!,\\&\textstyle \sum \limits _{k=0}^{n}2^{k}\displaystyle \left[{n \atop k}\right]=(n+1)!,\\&\textstyle \sum \limits _{k=0}^{n}(-1)^{k}\displaystyle \left[{n \atop k}\right]=0\quad (n\geq 2)\end{aligned}}} 第1の関係式は、 1 n ¯ = n ! {\displaystyle 1^{\overline {n}}=n!} から導かれる。第2の関係式は 2 n ¯ = ( n + 1 ) ! {\displaystyle 2^{\overline {n}}=(n+1)!} から導かれる。第3の関係式は n ≥ 2 {\displaystyle n\geq 2} に関して、 ( − 1 ) n ¯ = 0 {\displaystyle (-1)^{\overline {n}}=0} であることから導かれる。 第1種スターリング数はベルヌーイ数 B k {\displaystyle B_{k}} と次のような関係がある。 1 m ! ∑ k = 0 m [ m + 1 k + 1 ] B k = 1 m + 1 , 1 ( m − 1 ) ! ∑ k = 0 m [ m k ] B k = − 1 m + 1 ( m ≥ 1 ) . {\displaystyle {\begin{aligned}&{\frac {1}{m!}}\textstyle \sum \limits _{k=0}^{m}\displaystyle \left[{m+1 \atop k+1}\right]\,B_{k}={\frac {1}{m+1}},\\&{\frac {1}{(m-1)!}}\textstyle \sum \limits _{k=0}^{m}\displaystyle \left[{m \atop k}\right]\,B_{k}=-{\frac {1}{m+1}}\quad (m\geq 1).\end{aligned}}} 第1の関係式は、上昇階乗冪の和の公式： ∑ k = 0 n − 1 ( k + 1 ) m ¯ = n m + 1 ¯ m + 1 {\displaystyle \textstyle \sum \limits _{k=0}^{n-1}(k+1)^{\overline {m}}={\dfrac {n^{\overline {m+1}}}{m+1}}} から導くことができる。第2の関係式は、第1の関係式に第1種スターリング数の漸化式を適用すれば導かれる。 第1種スターリング数 [ n k ] {\displaystyle [{\textstyle {n \atop k}}]} は、組合せ数学において、 n {\displaystyle n} 個の要素を k {\displaystyle k} 個の巡回列に分割する組み合わせの数を与える。巡回列は山手線の駅のように繰り返される要素を示したデータ列である。ここでは、巡回列を ( 0 , 2 , 1 , 3 ) {\displaystyle (0,2,1,3)} のように書こう。この場合、0, 2, 1, 3の順に数値が繰り返される場合を意味する。巡回列の場合、順列ではあるが ( 0 , 2 , 1 , 3 ) {\displaystyle (0,2,1,3)} と ( 2 , 1 , 3 , 0 ) {\displaystyle (2,1,3,0)} のように要素を巡回置換した巡回列どうしは同一とみなす。したがって、 n {\displaystyle n} 個の要素で構成される巡回列の組み合わせは ( n − 1 ) ! {\displaystyle (n-1)!} 通りである。また、 ( 1 ) {\displaystyle (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通りとなる。この数値は [ 4 2 ] {\displaystyle [{\textstyle {4 \atop 2}}]} と一致する。そのような組み合わせをすべて列挙すると以下のようになる。 [ ( 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 ) ] {\displaystyle {\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}}} 上で説明した直接的な順列の作り方のほかに、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 {\displaystyle n} 個の要素から 巡回列 k {\displaystyle k} 個を作るには、手順1として、 n − 1 {\displaystyle n-1} 個の要素から 巡回列 k − 1 {\displaystyle k-1} 個を作った後、 k {\displaystyle k} 番目の巡回列として n {\displaystyle n} 番目の要素を単独で追加する。その組み合わせの数は、 n − 1 {\displaystyle n-1} 個の要素から 巡回列 k − 1 {\displaystyle k-1} 個を作る組み合わせの数に等しい。手順2として、 n − 1 {\displaystyle n-1} 個の要素から巡回列 k {\displaystyle k} 個を作った後、 n {\displaystyle n} 番目の要素を既存の巡回列に挿入する。その組み合わせの数は、 n − 1 {\displaystyle n-1} 個の要素から 巡回列 k {\displaystyle k} 個を作る組み合わせの数を n − 1 {\displaystyle n-1} 倍した値となる。手順1と手順2の組み合わせの和であることを考えると、 n {\displaystyle n} 個の要素から 巡回列 k {\displaystyle k} 個を作る組み合わせの数は第1スターリング数の漸化式で与えられることがわかる。したがって、その組み合わせの数は第1スターリング数 [ n k ] {\displaystyle [{\textstyle {n \atop k}}]} に等しい。 第2種スターリング数 (en:Stirling numbers of the second kind) { n k } {\displaystyle \{{\textstyle {n \atop k}}\}} は、 x n {\displaystyle x^{n}} を下降階乗冪 x k _ ≡ x ( x − 1 ) ( x − 2 ) ⋯ ( x − k + 1 ) {\displaystyle x^{\underline {k}}\equiv x\,(x-1)(x-2)\cdots (x-k+1)} の級数： x n = ∑ k = 0 n { n k } x k _ {\displaystyle x^{n}=\textstyle \sum \limits _{k=0}^{n}\displaystyle \left\{{n \atop k}\right\}\,x^{\underline {k}}} で展開したときの展開係数として定義される。この定義では、 0 ≤ k ≤ n {\displaystyle 0\leq k\leq n} である。便宜上、 { 0 0 } = 1 {\displaystyle \{{\textstyle {0 \atop 0}}\}=1} と定義する。第2種スターリング数は { n k } = { n − 1 k − 1 } + k { n − 1 k } {\displaystyle \left\{{n \atop k}\right\}=\left\{{n-1 \atop k-1}\right\}+k\,\left\{{n-1 \atop k}\right\}} なる漸化式で計算できる。この漸化式は、上記の級数展開による定義から導出できる。その漸化式に従うと、第2種スターリング数は下表のよう計算される。 第2種スターリング数 { n k } {\displaystyle \{{\textstyle {n \atop k}}\}} は、第1種スターリング数に符号補正を施した ( − 1 ) n + k [ n k ] {\displaystyle (-1)^{n+k}[{\textstyle {n \atop k}}]} に対して逆行列の関係、すなわち、 ∑ k = 0 N ( − 1 ) n + k [ n k ] { k m } = δ n m {\displaystyle \textstyle \sum \limits _{k=0}^{N}(-1)^{n+k}\displaystyle \left[{n \atop k}\right]\,\left\{{k \atop m}\right\}=\delta _{nm}} の関係を満たす。ただし、 N ≥ n , m {\displaystyle N\geq n,m} とする。また、 δ n m {\displaystyle \delta _{nm}} はクロネッカーのデルタである。この関係は、 x n {\displaystyle x^{n}} を下降階乗冪 x k _ {\displaystyle x^{\underline {k}}} で展開した数式に対し、 x k _ {\displaystyle x^{\underline {k}}} を x {\displaystyle x} のべき級数で展開すれば導出できる。べき乗 x n {\displaystyle x^{n}} は 上昇階乗冪 x k ¯ {\displaystyle x^{\overline {k}}} で展開した場合も、第2種スターリング数を含む展開係数を伴う。その展開した結果は、 x n = ∑ k n ( − 1 ) n + k { n k } x k ¯ {\displaystyle x^{n}=\textstyle \sum \limits _{k}^{n}(-1)^{n+k}\displaystyle \left\{{n \atop k}\right\}\,x^{\overline {k}}} となり、展開係数は第2種スターリング数に符号補正 ( − 1 ) n + k {\displaystyle (-1)^{n+k}} を施した値である。この展開式は、 x k _ = ( − 1 ) k ( − x ) k ¯ {\displaystyle x^{\underline {k}}=(-1)^{k}(-x)^{\overline {k}}} であることに注意すれば導出できる。 ∑ k = 1 n ( − 1 ) k ( k − 1 ) ! { n k } = 0 ( n ≥ 2 ) , ∑ k = 0 n ( − 1 ) n + k k ! { n k } = 1 , ∑ k = 0 n ( − 1 ) n + k ( k + 1 ) ! { n k } = 2 n {\displaystyle {\begin{aligned}&\textstyle \sum \limits _{k=1}^{n}(-1)^{k}(k-1)!\displaystyle \left\{{n \atop k}\right\}=0\quad \quad (n\geq 2),\\&\textstyle \sum \limits _{k=0}^{n}(-1)^{n+k}k!\displaystyle \left\{{n \atop k}\right\}=1,\\&\sum _{k=0}^{n}(-1)^{n+k}(k+1)!\left\{{n \atop k}\right\}=2^{n}\end{aligned}}} 第1の関係式は第2種スターリング数の漸化式から導出できる。第2の関係式は、 ( − 1 ) k _ = ( − 1 ) k k ! {\displaystyle (-1)^{\underline {k}}=(-1)^{k}k!} であることから導出できる。第3の関係式は ( − 2 ) k _ = ( − 1 ) k ( k + 1 ) ! {\displaystyle (-2)^{\underline {k}}=(-1)^{k}(k+1)!} から導出できる。 第2種スターリング数もベルヌーイ数との関係を示すことができる。 B k − 1 = ∑ m = 1 k ( − 1 ) k + m ( m − 1 ) ! m { k m } , B k = ∑ m = 0 k ( − 1 ) m m ! m + 1 { k m } {\displaystyle {\begin{aligned}&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{aligned}}} 第1の関係式は、第1種スターリング数とベルヌーイ数の関係式から導出できる。第2の関係式は、第1の関係式に第2種スターリング数の漸化式を適用すれば導出できる。さらに、第2種スターリング数は公式: { n k } = 1 k ! ∑ m = 1 k ( − 1 ) k − m ( k m ) m n {\displaystyle \left\{{n \atop k}\right\}={\frac {1}{k!}}\sum _{m=1}^{k}(-1)^{k-m}\left({k \atop m}\right)m^{n}} によって一般項が計算できる。しかし、この公式も総和記号を含んでいるため、漸化式よりも便利な公式とは言いがたいが、この公式をベルヌーイ数との関係式（第2の関係式）に代入すればベルヌーイ数の一般項を得ることができる。 第2種スターリング数 { n k } {\displaystyle \{{\textstyle {n \atop k}}\}} は、組合せ数学において、番号づけされた n {\displaystyle n} 個の要素をグループ k {\displaystyle k} 個に分割する組み合わせの数を与える。分割する要素は番号付けされているので個別に区別できるが、グループは順序を特に区別しないものとする。選択された要素を ( 0 , 2 , 3 ) {\displaystyle (0,2,3)} と書いた場合、 ( 0 , 3 , 2 ) {\displaystyle (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通りがある。 [ ( 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 ) ] {\displaystyle {\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}}} 上で列挙した要素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 {\displaystyle n} 個をグループ k {\displaystyle k} 個に分割するには、次の2つの手順で組み合わせを作ればよい。手順1として、要素 n − 1 {\displaystyle n-1} 個をグループ k − 1 {\displaystyle k-1} 個に分割し、 n {\displaystyle n} 番目の要素を k {\displaystyle k} 番目のグループとして単独で追加すればよい。手順2として、要素 n − 1 {\displaystyle n-1} 個をグループ k {\displaystyle k} 個に分割し、 n {\displaystyle n} 番目の要素を k {\displaystyle k} 個のグループのどれかに挿入する。手順1で構成される組み合わせの数は、要素 n − 1 {\displaystyle n-1} 個をグループ k − 1 {\displaystyle k-1} 個に分割する組み合わせの数に等しい。手順2で構成される組み合わせの数は、要素 n − 1 {\displaystyle n-1} 個をグループ k {\displaystyle k} に分割する組み合わせの数の k {\displaystyle k} 倍に等しい。したがって、手順1と手順2で構成される組み合わせの和として、求める組み合わせの数は第2種スターリング数の漸化式で与えられる。要素 n {\displaystyle n} 個をグループ k {\displaystyle k} 個に分割する組み合わせは、第2種スターリング数 { n k } {\displaystyle \{{\textstyle {n \atop k}}\}} で与えられる。