スターリング数

**スターリング数**（スターリングすう、）は、上昇階乗冪 () や下降階乗冪 () を数値の冪乗と関係づけるための級数の展開係数として、イギリスの数学者が1730年に彼の著書 *Methodus Differentialis* で導入した数である。スターリング数は第1種スターリング数と、第2種スターリング数に分類される。第1種スターリング数はべき乗から階乗への変換に、第2種スターリング数は階乗からべき乗への変換に現れる。また、スターリング数は組合せ数学において意味をもった数値を与える。角括弧・波括弧による記法はヨヴァン・カラマタによって導入され、ドナルド・クヌースによって普及した。

## 第1種スターリング数
第1種スターリング数 (:en:Stirling numbers of the first kind) [{\textstyle{n\atop k}}] は、上昇階乗冪 x^{\overline{n}}\equiv x(x+1)(x+2)\cdots(x+n-1) を x のべき級数：
:x^{\overline{n}} = \textstyle\sum\limits_{k=0}^n \displaystyle \left[{n\atop k}\right]\,x^k
で表現したときの展開係数として定義される。この定義では 0\leq k\leq n である。また、便宜上 [{\textstyle{0\atop0}}] = 1 と定義する。第1種スターリング数は、
:\left[{n\atop k}\right] = \left[{n-1\atop k-1}\right] + (n-1)\,\left[{n-1\atop k}\right]
なる漸化式で計算できる。この漸化式は、べき級数の展開係数としての定義から導出できる。第1種スターリング数の中で、簡単な数式で書ける成分として、
:
   \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

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

下降階乗冪 x^{\underline{n}}\equiv x\,(x-1)(x-2)\cdots(x-n+1) も第1種スターリング数を含む展開係数を伴い、x のべき級数で表現できる。具体的には、
:x^{\underline{n}} = \textstyle\sum\limits_{k=0}^n (-1)^{n+k} \displaystyle \left[ {n\atop k}\right]\,x^k
と書けるので、展開係数は第1種スターリング数に符号補正 (-1)^{n+k} を施した値である。この展開式は、
:\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}
であることに注意すれば容易に証明できる。

### 第1種スターリング数の性質
:\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}
第1の関係式は、1^{\overline{n}}=n! から導かれる。第2の関係式は 2^{\overline{n}}=(n+1)! から導かれる。第3の関係式は n\geq2 に関して、(-1)^{\overline{n}}=0 であることから導かれる。

第1種スターリング数はベルヌーイ数 B_k と次のような関係がある。
:\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}
第1の関係式は、上昇階乗冪の和の公式：
:\textstyle\sum\limits_{k=0}^{n-1} (k+1)^{\overline{m}} = \dfrac{n^{\overline{m+1}}}{m+1}
から導くことができる。第2の関係式は、第1の関係式に第1種スターリング数の漸化式を適用すれば導かれる。

### 組み合わせ数学における意味
第1種スターリング数 [{\textstyle{n\atop 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通りとなる。この数値は [{\textstyle{4\atop2}}] と一致する。そのような組み合わせをすべて列挙すると以下のようになる。
:\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 個の要素から 巡回列 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スターリング数 [{\textstyle{n\atop k}}] に等しい。

## 第2種スターリング数
第2種スターリング数 (:en:Stirling numbers of the second kind) \\} は、x^n を下降階乗冪 x^{\underline{k}}\equiv x\,(x-1)(x-2)\cdots(x-k+1) の級数：
:x^n = \textstyle\sum\limits_{k=0}^n \displaystyle\left\
で展開したときの展開係数として定義される。この定義では、0\leq k\leq n である。便宜上、\\}=1 と定義する。第2種スターリング数は
:\left\ を x のべき級数で展開すれば導出できる。べき乗 x^n は 上昇階乗冪 x^{\overline{k}}
で展開した場合も、第2種スターリング数を含む展開係数を伴う。その展開した結果は、
:x^n = \textstyle\sum\limits_k^n (-1)^{n+k} \displaystyle\left\
となり、展開係数は第2種スターリング数に符号補正 (-1)^{n+k} を施した値である。この展開式は、x^{\underline{k}}=(-1)^k(-x)^{\overline{k}} であることに注意すれば導出できる。

### 第2種スターリング数の性質
:\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\=(-1)^k(k+1)! から導出できる。

第2種スターリング数もベルヌーイ数との関係を示すことができる。
:\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\\} で与えられる。

## 脚注

## 関連項目
* 
* 
* 集合の分割
* ベル数
* 階乗冪

## 外部リンク
*