スターリング数の漸化式と3つの意味

まず，任意の自然数 $n$ に対して $S(n,1)=S(n,n)=1$ は自明。

あとは漸化式が成立すること証明する。

$S(n,k)$ は以下の $2$ つの場合の数の和で表される。

• まず特定の $n-1$ 個のものを $k-1$ グループに分けておいて最後の $1$ つを $k$ グループ目とする場合の数
• まず特定の $n-1$ 個のものを $k$ グループに分けておいて最後の $1$ つをいずれかに加える場合の数

ひとつめは $S(n-1,k-1)$ 通りでふたつめが $kS(n-1,k)$ 通りなので「性質1」の漸化式が成立する。

$x^n=\displaystyle\sum_{k=1}^nS(n,k)f_k(x)$

において最高次の係数を比較すると $S(n,n)=1$ が分かる。

また，$x=1$ を代入すると $S(n,1)=1$ が分かる。

あとは漸化式を示すのが目標なので $x^{n-1}$ の展開式を変形して $x^n$ の展開式を作っていく。

$x^{n-1}=\displaystyle\sum_{k=1}^{n-1}S(n-1,k)f_k(x)\\ =\displaystyle\sum_{k=2}^{n}S(n-1,k-1)f_{k-1}(x)$

この両辺に $x$ をかけて $x=(x-k+1)+(k-1)$ であることに注意すると，

$x^n=\displaystyle\sum_{k=2}^{n}S(n-1,k-1)(x-k+1)f_{k-1}(x)\\+\displaystyle\sum_{k=2}^{n}S(n-1,k-1)(k-1)f_{k-1}(x)\\ =\displaystyle\sum_{k=2}^nS(n-1,k-1)f_{k}(x) +\displaystyle\sum_{k=1}^{n-1}S(n-1,k)kf_{k}(x)\:\:(※)$

ここで右辺第一項は $f_{k}(x)$ の定義を使い，第二項は添字を平行移動させた。

$f_k(x)$ の係数を比較して性質1の漸化式を得る。

帰納法で示す。 $n-1$ のときまで性質3が正しいと仮定すると，上式の(※)と性質1より $n$ のときも成立。