第2種スターリング数の一般解
第2種スターリング数の一般解
第2種スターリング数は次の式で表される。
\[ S_{2}\left(n,k\right)=\frac{1}{k!}\sum_{j=0}^{k}\left(-1\right)^{k-j}C\left(k,j\right)j^{n} \]
第2種スターリング数は次の式で表される。
\[ S_{2}\left(n,k\right)=\frac{1}{k!}\sum_{j=0}^{k}\left(-1\right)^{k-j}C\left(k,j\right)j^{n} \]
-
\(S_{2}\left(n,k\right)\)は第2種スターリング数\begin{align*}
S_{2}\left(3,2\right) & =\frac{1}{2!}\sum_{j=0}^{2}\left(-1\right)^{2-j}C\left(2,j\right)j^{3}\\
& =\frac{1}{2!}\left\{ \left(-1\right)^{2}C\left(2,0\right)0^{3}+\left(-1\right)^{2-1}C\left(2,1\right)1^{3}+\left(-1\right)^{2-2}C\left(2,2\right)2^{3}\right\} \\
& =\frac{1}{2!}\left(0-2+8\right)\\
& =\frac{6}{2}\\
& =3
\end{align*}
(0)
組み合わせ論的解釈区別の出来る\(n\)個の玉を区別の出来ない\(k\)個の箱に分けるとき、空箱ありの場合の数は\(k^{n}\)で空箱なしの場合の数は\(S_{2}\left(n,j\right)\)となる。
区別の出来ないの箱のとき、空箱ありとなしとの場合の数の関係より、
\[ k^{n}=\sum_{j=0}^{k}C\left(k,j\right)S_{2}\left(n,j\right)j! \] となる。
これは2項変換なので逆変換は、
\[ S_{2}\left(n,k\right)=\frac{1}{k!}\sum_{j=0}^{k}\left(-1\right)^{k-j}C\left(k,j\right)j^{n} \] となり与式は成り立つ。
(0)-2
\(n=0\)のとき\begin{align*} S_{2}\left(0,k\right) & =\frac{1}{k!}\sum_{j=0}^{k}\left(-1\right)^{k-j}C\left(k,j\right)j^{0}\\ & =\frac{\left(-1\right)^{k}}{k!}\sum_{j=0}^{k}\left(-1\right)^{j}C\left(k,j\right)\\ & =\frac{\left(-1\right)^{k}}{k!}\delta_{0,k}\\ & =\delta_{0,k} \end{align*} となるので\(k\)の値に依らずに成り立つ。
\(n=m\)のとき成り立つと仮定する。
\begin{align*} S_{2}\left(m+1,k\right) & =S_{2}\left(m,k-1\right)+kS_{2}\left(m,k\right)\\ & =\frac{1}{\left(k-1\right)!}\sum_{j=0}^{k-1}\left(-1\right)^{k-1-j}C\left(k-1,j\right)j^{m}+k\frac{1}{k!}\sum_{j=0}^{k}\left(-1\right)^{k-j}C\left(k,j\right)j^{m}\\ & =\frac{1}{\left(k-1\right)!}\sum_{j=0}^{k}\left(-1\right)^{k-j}\left\{ C\left(k,j\right)-C\left(k-1,j\right)\right\} j^{m}\\ & =\frac{1}{\left(k-1\right)!}\sum_{j=0}^{k}\left(-1\right)^{k-j}C\left(k-1,j-1\right)j^{m}\\ & =\frac{1}{k!}\sum_{j=0}^{k}\left(-1\right)^{k-j}C\left(k,j\right)j^{m+1} \end{align*} これより\(n=m+1\)で成り立つ。
従って数学的帰納法より与式は成り立つ。
ページ情報
タイトル | 第2種スターリング数の一般解 |
URL | https://www.nomuramath.com/ou31d0q2/ |
SNSボタン |
スターリング数の組み合わせ解釈
第1種スターリング数と第2種スターリング数の定義
\[
P\left(x,n\right)=\sum_{k=0}^{n}S_{1}\left(n,k\right)x^{k}
\]
(*)スターリング数の漸化式
\[
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)
\]
スターリング数と上昇・下降階乗
\[
Q\left(x,n\right)=\sum_{k=0}^{n}\left(-1\right)^{n+k}S_{1}\left(n,k\right)x^{k}
\]