Stirling数その2
Stirling数その1では第1種Stirling数を定義した、 ここでは第2種Stirling数を定義する。
\[ x^n=\sum_{k=0}^nS_{n,k}x^{\underline{k}} \] ここで、\(x^{\underline{n}}=x(x-1)\cdots(x-n+1)\)は下降べきである。\(S_{n,k}\)を第2種Stirling数という。 上記の添字の範囲外では\(0\)と定義する。\(x=-1,-2\)とすると、それぞれ、 \begin{align} \sum_{k=0}^n(-1)^{n-k}k!S_{n,k}&=1\\ \sum_{k=0}^n(-1)^{n-k}(k+1)!S_{n,k}&=2^n \end{align} さて、これの漸化式を得たい。 \begin{align} \sum_{k=0}^{n+1}S_{n+1,k}x^{\underline{k}}&=x^{n+1}\\ &=x\sum_{k=0}^{n}S_{n,k}x^{\underline{k}}\\ &=\sum_{k=0}^{n}(x-k)S_{n,k}x^{\underline{k}}+\sum_{k=0}^nkS_{n,k}x^{\underline{k}}\\ &=\sum_{k=0}^nS_{n,k}x^{\underline{k+1}}+\sum_{k=0}^nkS_{n,k}x^{\underline{k}}\\ &=\sum_{k=0}^{n+1}S_{n,k-1}x^{\underline{k}}+\sum_{k=0}^{n+1}kS_{n,k}x^{\underline{k}}\\ &=\sum_{k=0}^{n+1}(S_{n,k-1}+kS_{n,k})x^{\underline{k}} \end{align} よって、漸化式 \[ S_{n+1,k}=S_{n,k-1}+kS_{n,k} \] が得られた。これをもちいて具体的に計算すると、 \begin{align} \begin{array}{ccccc} 1\\ 0 & 1\\ 0 & 1 & 1\\ 0 & 1 & 3 & 1\\ 0 & 1 & 7 & 6 & 1\\ 0 & 1 & 15 & 25 & 10 & 1 \end{array} \end{align} のようになる。 \[ x^n=\sum_{k=0}^nS_{n,k}x^{\underline{k}} \] の両辺を\(m\)階差分すると、 \[ \sum_{l=0}^m(-1)^{m-i}\binom{m}{i}(x+i)^n=\sum_{k=0}^nS_{n,k}\frac{k!}{(k-m)!}x^{\underline{k-m}} \] 差分は前進差分とする。ここで、\(x=0\)を代入すると、 \[ \sum_{i=0}^m(-1)^{m-i}\binom{m}{i}i^n=m!S_{n,m} \] よって、 \[ S_{n,k}=\frac{1}{k!}\sum_{i=0}^k(-1)^{k-i}\binom{k}{i}i^n \] これが、第2種Stirling数の一般項である。 ここで、第1種Stirling数の式 \[ x^n=\sum_{k=0}^n(-1)^{n-k}s_{n,k}x^{\underline{k}} \] の下降べきに最初の式を代入してみよう。 \begin{align} x^n&=\sum_{k=0}^n(-1)^{n-k}s_{n,k}x^{\underline{k}}\\ &=\sum_{k=0}^n(-1)^{n-k}s_{n,k}\sum_{m=0}^kS_{k,m}x^m\\ &=\sum_{m=0}^nx^m\sum_{k=0}^n(-1)^{n-k}s_{n,k}S_{k,m}\\ \end{align} よって、 \[ \sum_{k=0}^n(-1)^{n-k}s_{n,k}S_{k,m}=\delta_{nm}\\ \] であるから、\(s=((-1)^{i+j}s_{i,j}),\,S=(S_{i,j}),\quad(1\leq i,j\leq n)\)を行列と見たものは、 互いに逆行列の関係になる。