スターリング数
第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種スターリング数の漸化式を適用すれば導かれる。
前者の分割法では、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}}]} と一致する。そのような組み合わせをすべて列挙すると以下のようになる。
∑ 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)!} から導出できる。
第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} のべき級数で表現できる。