(*)スターリング数の漸化式
スターリング数の漸化式
スターリング数は次の漸化式を満たす。
第1種スターリング数
\[ S_{1}\left(n,k\right)=S_{1}\left(n-1,k-1\right)-\left(n-1\right)S_{1}\left(n-1,k\right) \]
\[ S_{1}\left(n+1,k+1\right)=n!\sum_{j=k}^{n}\frac{\left(-1\right)^{n-j}}{j!}S_{1}\left(j,k\right) \]
\[ S_{1}\left(n+k+1,k\right)=-\sum_{j=0}^{k}\left(n+j\right)S_{1}\left(n+j,j\right) \]
\[ S_{1}\left(n,k\right)=\sum_{j=0}^{n-k}S_{1}\left(n+1,k+j+1\right)n^{j} \]
第2種スターリング数
\[ S_{2}\left(n,k\right)=S_{2}\left(n-1,k-1\right)+kS_{2}\left(n-1,k\right) \]
\[ S_{2}\left(n,k\right)=\sum_{j=k}^{n}S_{2}\left(j-1,k-1\right)k^{n-j} \]
\[ S_{2}\left(n+k+1,k\right)=\sum_{j=0}^{k}jS_{2}\left(n+j,j\right) \]
\[ S_{2}\left(n+1,k+1\right)=\sum_{j=k}^{n}C\left(n,j\right)S_{2}\left(j,k\right),n\in\mathbb{N}_{0} \]
\(S_{2}\left(n,k\right)\)は第2種スターリング数
スターリング数は次の漸化式を満たす。
第1種スターリング数
(1)基本
\(n,k\in\mathbb{N}\)とする。\[ S_{1}\left(n,k\right)=S_{1}\left(n-1,k-1\right)-\left(n-1\right)S_{1}\left(n-1,k\right) \]
(2)
\(n,k\in\mathbb{N}_{0}\)とする。\[ S_{1}\left(n+1,k+1\right)=n!\sum_{j=k}^{n}\frac{\left(-1\right)^{n-j}}{j!}S_{1}\left(j,k\right) \]
(3)
\(n,k\in\mathbb{N}_{0}\)とする。\[ S_{1}\left(n+k+1,k\right)=-\sum_{j=0}^{k}\left(n+j\right)S_{1}\left(n+j,j\right) \]
(4)
\(n,k\in\mathbb{N}_{0}\)とする。\[ S_{1}\left(n,k\right)=\sum_{j=0}^{n-k}S_{1}\left(n+1,k+j+1\right)n^{j} \]
(5)
\[ S_{1}\left(n,k\right)=\sum_{j=0}^{n-k}\left(-1\right)^{n+k}S_{1}\left(n,j+k\right)C\left(j+k,k\right)\left(n-1\right)^{j} \]第2種スターリング数
(6)基本
\(n,k\in\mathbb{N}\)とする。\[ S_{2}\left(n,k\right)=S_{2}\left(n-1,k-1\right)+kS_{2}\left(n-1,k\right) \]
(7)
\(n,k\in\mathbb{N}\)とする。\[ S_{2}\left(n,k\right)=\sum_{j=k}^{n}S_{2}\left(j-1,k-1\right)k^{n-j} \]
(8)
\(n,k\in\mathbb{N}_{0}\)とする。\[ S_{2}\left(n+k+1,k\right)=\sum_{j=0}^{k}jS_{2}\left(n+j,j\right) \]
(9)
\(n,k\in\mathbb{N}_{0}\)とする。\[ S_{2}\left(n+1,k+1\right)=\sum_{j=k}^{n}C\left(n,j\right)S_{2}\left(j,k\right),n\in\mathbb{N}_{0} \]
-
\(S_{1}\left(n,k\right)\)は第1種スターリング数\(S_{2}\left(n,k\right)\)は第2種スターリング数
(1)
\begin{align*} \sum_{k=0}^{n}S_{1}\left(n,k\right)x^{k} & =P\left(x,n\right)\\ & =\left(x-n+1\right)P\left(x,n-1\right)\\ & =\left(x-n+1\right)\sum_{k=0}^{n-1}S_{1}\left(n-1,k\right)x^{k}\\ & =\sum_{k=0}^{n-1}S_{1}\left(n-1,k\right)x^{k+1}-\sum_{k=0}^{n-1}\left(n-1\right)S_{1}\left(n-1,k\right)x^{k}\\ & =\sum_{k=1}^{n}S_{1}\left(n-1,k-1\right)x^{k}-\sum_{k=0}^{n-1}\left(n-1\right)S_{1}\left(n-1,k\right)x^{k}\\ & =\sum_{k=0}^{n}S_{1}\left(n-1,k-1\right)x^{k}-\sum_{k=0}^{n}\left(n-1\right)S_{1}\left(n-1,k\right)x^{k}\\ & =\sum_{k=0}^{n}\left\{ S_{1}\left(n-1,k-1\right)-\left(n-1\right)S_{1}\left(n-1,k\right)\right\} x^{k} \end{align*} これより、\begin{align*} S_{1}\left(n,k\right) & =S_{1}\left(n-1,k-1\right)-\left(n-1\right)S_{1}\left(n-1,k\right) \end{align*}
(2)
\begin{align*} S_{1}\left(n+1,k+1\right) & =\left(-1\right)^{n+k+2}\frac{n!}{k!}S_{1}\left(k+1,k+1\right)+\left(-1\right)^{n}n!\sum_{j=k+2}^{n+1}\left(\frac{\left(-1\right)^{j-1}}{\left(j-1\right)!}S_{1}\left(j,k+1\right)-\frac{\left(-1\right)^{j}}{\left(j-2\right)!}S_{1}\left(j-1,k+1\right)\right)\\ & =\left(-1\right)^{n+k}\frac{n!}{k!}+\left(-1\right)^{n}n!\sum_{j=k+2}^{n+1}\left(\frac{\left(-1\right)^{j-1}}{\left(j-1\right)!}S_{1}\left(j-1,k\right)\right)\\ & =\left(-1\right)^{n+k}\frac{n!}{k!}S_{1}\left(k,k\right)+n!\sum_{j=k+1}^{n}\left(\frac{\left(-1\right)^{n+j}}{j!}S_{1}\left(j,k\right)\right)\\ & =n!\sum_{j=k}^{n}\left(\frac{\left(-1\right)^{n+j}}{j!}S_{1}\left(j,k\right)\right) \end{align*}(3)
\begin{align*} S_{1}\left(n+k+1,k\right) & =S_{1}\left(n+1,0\right)+\sum_{j=1}^{k}\left(S_{1}\left(n+j+1,j\right)-S_{1}\left(n+j,j-1\right)\right)\\ & =\delta_{0,n+1}-\sum_{j=1}^{k}\left(\left(n+j\right)S_{1}\left(n+j,j\right)\right)\\ & =\delta_{0,n+1}-n\delta_{0,n}-\sum_{j=0}^{k}\left(\left(n+j\right)S_{1}\left(n+j,j\right)\right)\\ & =-\sum_{j=0}^{k}\left(\left(n+j\right)S_{1}\left(n+j,j\right)\right)\cmt{\because n\in\mathbb{N}_{0}} \end{align*}(4)
略(5)
\begin{align*} \sum_{k=0}^{n}S_{1}\left(n,k\right)x^{k} & =P\left(x,n\right)\\ & =\left(-1\right)^{n}P\left(-x+n-1,n\right)\\ & =\left(-1\right)^{n}\sum_{k=0}^{n}S_{1}\left(n,k\right)\left(-x+n-1\right)^{k}\\ & =\left(-1\right)^{n}\sum_{k=0}^{n}S_{1}\left(n,k\right)\sum_{j=0}^{k}C\left(k,j\right)\left(-x\right)^{j}\left(n-1\right)^{k-j}\\ & =\left(-1\right)^{n}\sum_{j=0}^{n}\sum_{k=j}^{n}S_{1}\left(n,k\right)C\left(k,j\right)\left(-x\right)^{j}\left(n-1\right)^{k-j}\\ & =\sum_{j=0}^{n}x^{j}\sum_{k=j}^{n}\left(-1\right)^{n+j}S_{1}\left(n,k\right)C\left(k,j\right)\left(n-1\right)^{k-j}\\ & =\sum_{k=0}^{n}x^{k}\sum_{j=k}^{n}\left(-1\right)^{n+k}S_{1}\left(n,j\right)C\left(j,k\right)\left(n-1\right)^{j-k} \end{align*} 係数を比較すると、\begin{align*} S_{1}\left(n,k\right) & =\sum_{j=k}^{n}\left(-1\right)^{n+k}S_{1}\left(n,j\right)C\left(j,k\right)\left(n-1\right)^{j-k}\\ & =\sum_{j=0}^{n-k}\left(-1\right)^{n+k}S_{1}\left(n,j+k\right)C\left(j+k,k\right)\left(n-1\right)^{j} \end{align*} となるので与式は成り立つ。
(6)
\begin{align*} \sum_{k=0}^{n}S_{2}\left(n,k\right)P\left(x,k\right) & =x^{n}\\ & =xx^{n-1}\\ & =\left(x-k+k\right)\sum_{k=0}^{n-1}S_{2}\left(n-1,k\right)P\left(x,k\right)\\ & =\sum_{k=0}^{n-1}S_{2}\left(n-1,k\right)\left(x-k\right)P\left(x,k\right)+\sum_{k=0}^{n-1}kS_{2}\left(n-1,k\right)P\left(x,k\right)\\ & =\sum_{k=0}^{n-1}S_{2}\left(n-1,k\right)P\left(x,k+1\right)+\sum_{k=0}^{n-1}kS_{2}\left(n-1,k\right)P\left(x,k\right)\\ & =\sum_{k=1}^{n}S_{2}\left(n-1,k-1\right)P\left(x,k\right)+\sum_{k=0}^{n-1}kS_{2}\left(n-1,k\right)P\left(x,k\right)\\ & =\sum_{k=0}^{n}S_{2}\left(n-1,k-1\right)P\left(x,k\right)+\sum_{k=0}^{n}kS_{2}\left(n-1,k\right)P\left(x,k\right)\\ & =\sum_{k=0}^{n}\left\{ S_{2}\left(n-1,k-1\right)+kS_{2}\left(n-1,k\right)\right\} P\left(x,k\right) \end{align*} これより、\[ S_{2}\left(n,k\right)=S_{2}\left(n-1,k-1\right)+kS_{2}\left(n-1,k\right) \]
(7)
\begin{align*} S_{2}\left(n,k\right) & =S_{2}\left(0,k\right)+k^{n}\sum_{j=1}^{n}\left(\frac{1}{k^{j}}S_{2}\left(j,k\right)-\frac{1}{k^{j-1}}S_{2}\left(j-1,k\right)\right)\\ & =\delta_{0,k}+k^{n}\sum_{j=1}^{n}\frac{1}{k^{j}}S_{2}\left(j-1,k-1\right)\\ & =\delta_{0,k}+\sum_{j=k}^{n}k^{n-j}S_{2}\left(j-1,k-1\right)\\ & =\sum_{j=k}^{n}k^{n-j}S_{2}\left(j-1,k-1\right)\cmt{\because k\in\mathbb{N}_{0}} \end{align*}(8)
\begin{align*} S_{2}\left(n+k+1,k\right) & =S_{2}\left(n+1,0\right)+\sum_{j=1}^{k}\left\{ S_{2}\left(n+j+1,j\right)-S_{2}\left(n+j,j-1\right)\right\} \\ & =\delta_{0,n+1}+\sum_{j=1}^{k}jS_{2}\left(n+j,j\right)\\ & =\delta_{0,n+1}+\sum_{j=0}^{k}jS_{2}\left(n+j,j\right)\\ & =\sum_{j=0}^{k}jS_{2}\left(n+j,j\right)\cmt{\because n\in\mathbb{N}_{0}} \end{align*}(9)
\begin{align*} \sum_{j=k}^{n}C\left(n,j\right)S_{2}\left(j,k\right) & =\sum_{j=0}^{n}C\left(n,j\right)S_{2}\left(j,k\right)\\ & =\sum_{j=0}^{n}C\left(n,j\right)\frac{1}{k!}\sum_{m=0}^{k}\left(-1\right)^{k-m}C\left(k,m\right)m^{j}\\ & =\sum_{m=0}^{k}\frac{1}{k!}\left(-1\right)^{k-m}C\left(k,m\right)\sum_{j=0}^{n}C\left(n,j\right)m^{j}\\ & =\sum_{m=0}^{k}\frac{1}{k!}\left(-1\right)^{k-m}C\left(k,m\right)\left(1+m\right)^{n}\\ & =\sum_{m=0}^{k}\frac{1}{\left(k+1\right)!}\left(-1\right)^{k-m}C\left(k+1,m+1\right)\left(1+m\right)^{n+1}\\ & =\sum_{m=1}^{k+1}\frac{1}{\left(k+1\right)!}\left(-1\right)^{k-m+1}C\left(k+1,m\right)m^{n+1}\\ & =\sum_{m=0}^{k+1}\frac{1}{\left(k+1\right)!}\left(-1\right)^{k+1-m}C\left(k+1,m\right)m^{n+1}-\frac{1}{\left(k+1\right)!}\left(-1\right)^{k+1}\delta_{0,n+1}\\ & =S_{2}\left(n+1,k+1\right)-\frac{1}{\left(k+1\right)!}\left(-1\right)^{k+1}\delta_{0,n+1}\\ & =S_{2}\left(n+1,k+1\right)\cmt{\because n\in\mathbb{N}_{0}} \end{align*}ページ情報
タイトル | (*)スターリング数の漸化式 |
URL | https://www.nomuramath.com/dh0x6xv9/ |
SNSボタン |
第1種・第2種スターリング数の性質
\[
\sum_{k=0}^{n}\left(-1\right)^{n+k}S_{1}\left(n,k\right)=n!
\]
スターリング数と上昇・下降階乗
\[
Q\left(x,n\right)=\sum_{k=0}^{n}\left(-1\right)^{n+k}S_{1}\left(n,k\right)x^{k}
\]
スターリング数とベルヌーイ数の関係
\[
\frac{\left(-1\right)^{m}}{m!}\sum_{k=0}^{m}\left(-1\right)^{k}S_{1}\left(m+1,k+1\right)B_{k}=\frac{1}{m+1}
\]
スターリング数の解釈
\[
\left(-1\right)^{n+k}S_{1}\left(n,k\right)=\sum_{1\leq a_{1}<a_{2}<\cdots<a_{n-k}\leq n-1}\prod_{j=1}^{n-k}a_{j}
\]