スターリング数のソースを表示

'''スターリング数'''（スターリングすう、{{lang-en-short|Stirling number}}）は、[[上昇階乗冪]] ({{en|rising factorial}}) や[[下降階乗冪]] ({{en|falling factorial}}) を数値の[[冪乗]]と関係づけるための[[級数]]の展開係数として、イギリスの数学者{{仮リンク|ジェームズ・スターリング (数学者)|label=ジェームズ・スターリング|en|James Stirling (mathematician)}}が1730年に彼の著書 ''Methodus Differentialis'' で導入した数<ref>Charalambos A., Charalambides, "Combinatorial Methods in Discrete Distributions," John Wiley & Sons, Inc., p.73, 2005.</ref>である。スターリング数は第1種スターリング数と、第2種スターリング数に分類される。第1種スターリング数はべき乗から階乗への変換に、第2種スターリング数は階乗からべき乗への変換に現れる。また、スターリング数は[[組合せ数学]]において意味をもった数値を与える。

== 第1種スターリング数 ==
第1種スターリング数 ([[:en:Stirling numbers 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}} = \textstyle\sum\limits_{k=0}^n \displaystyle \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種スターリング数は下表のように計算される。なお、表中の空欄に位置する数値はゼロであると解釈する。
{|class="wikitable" cellspacing="0" cellpadding="3" style="text-align:right"
!''n'' ＼ ''k''
!style="width:11%"|''0''
!style="width:11%"|''1''
!style="width:11%"|''2''
!style="width:11%"|''3''
!style="width:11%"|''4''
!style="width:11%"|''5''
!style="width:11%"|''6''
!style="width:11%"|''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}} = \textstyle\sum\limits_{k=0}^n (-1)^{n+k} \displaystyle \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}
   &\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\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!} \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\geq1).
\end{align}</math>
第1の関係式は、上昇階乗冪の和の公式：
:<math>\textstyle\sum\limits_{k=0}^{n-1} (k+1)^{\overline{m}} = \dfrac{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種スターリング数 ([[:en:Stirling numbers 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 = \textstyle\sum\limits_{k=0}^n \displaystyle\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種スターリング数は下表のよう計算される。
{|class="wikitable" cellspacing="0" cellpadding="3" style="text-align:right"
!''n'' ＼ ''k''
!style="width:11%"|''0''
!style="width:11%"|''1''
!style="width:11%"|''2''
!style="width:11%"|''3''
!style="width:11%"|''4''
!style="width:11%"|''5''
!style="width:11%"|''6''
!style="width:11%"|''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>\textstyle\sum\limits_{k=0}^N (-1)^{n+k} \displaystyle\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 = \textstyle\sum\limits_k^n (-1)^{n+k} \displaystyle\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}
  &\textstyle\sum\limits_{k=1}^n (-1)^k(k-1)! \displaystyle\left\{{n\atop k}\right\}=0\quad\quad(n\geq2),\\
  &\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{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> で与えられる。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
* {{ill|スターリング多項式|en|Stirling polynomials}}
* {{ill|スターリング変換|en|Stirling transform}}
* [[集合の分割]]
* [[ベル数]]
* [[階乗冪]]

== 外部リンク ==
* {{高校数学の美しい物語|841|スターリング数の漸化式と3つの意味}}

{{二項演算}}
{{DEFAULTSORT:すたありんくすう}}
[[Category:組合せ論]]
[[Category:順列]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]