読者です 読者をやめる 読者になる 読者になる

スターリング数

S(m,n)をm個の集合からn個の集合への全射の総数とする。
S(m,n):=|\{f\in B^A|f:全射,|A|=m,|B|=n\}|
以下の漸化式が成り立つ。
 S(m,0)=0^m\\
\displaystyle S(m,n)=n^m-\sum_{k=0}^{n-1}\left(\begin{matrix}n\\k\end{matrix}\right)S(m,k)
nを固定して求める。
\displaystyle 
\begin{eqnarray}
S(m,1)&=&1^m-\sum_{k=0}^{0}\left(\begin{matrix} 1 \\k\end{matrix}\right)S(m,k)\\
&=&1^m-\left(\begin{matrix} 1 \\0\end{matrix}\right)S(m,0)\\
&=&1^mー0^m\\
S(m,2)&=&2^m-\sum_{k=0}^{1}\left(\begin{matrix}2 \\k\end{matrix}\right)S(m,k)\\
&=&2^m-\left(\begin{matrix}2 \\1\end{matrix}\right)S(m,1)-\left(\begin{matrix}2 \\0\end{matrix}\right)S(m,0)\\
&=&2^m-2(1^m-0^m)-0^m\\
&=&2^m-2\cdot1^m+0^m\\
S(m,3)&=&3^m-\sum_{k=0}^{2}\left(\begin{matrix}3 \\k\end{matrix}\right)S(m,k)\\
&=&3^m-\left(\begin{matrix}3 \\2\end{matrix}\right)S(m,2)-\left(\begin{matrix}3 \\1\end{matrix}\right)S(m,1)-\left(\begin{matrix}3 \\0\end{matrix}\right)S(m,0)\\
&=&3^m-3(2^m-2\cdot1^m+0^m)-3(1^mー0^m)-0^m\\
&=&3^m-3\cdot2^m+3\cdot1^m-0^m\\
S(m,4)&=&4^m-\sum_{k=0}^{3}\left(\begin{matrix} 4 \\k\end{matrix}\right)S(m,k)\\
&=&4^m-\left(\begin{matrix} 4 \\3\end{matrix}\right)S(m,3)-\left(\begin{matrix} 4 \\2\end{matrix}\right)S(m,2)-\left(\begin{matrix} 4 \\1\end{matrix}\right)S(m,1)-\left(\begin{matrix} 4 \\0\end{matrix}\right)S(m,0)\\
&=&4^m-4(3^m-3\cdot2^m+3\cdot1^m-0^m)-6(2^m-2\cdot1^m+0^m)\\
&&-4(1^mー0^m)-0^m\\
&=&4^m-4\cdot3^m+6\cdot2^m-4\cdot1^m+0^m
\end{eqnarray}
どうやら、S(m,n)は次の式になるようだ。
\displaystyle S(m,n)=\sum_{k=0}^n \left(\begin{matrix}n\\k\end{matrix}\right) (-1)^{n-k} k^m
以下、数学的帰納法で証明する。
\displaystyle
\begin{eqnarray}
S(m,n)&=&n^m-\sum_{k=0}^{n-1}\left(\begin{matrix}n\\k\end{matrix}\right)S(m,k)\\
&=&n^m-\sum_{k=0}^{n-1}\left(\begin{matrix}n\\k\end{matrix}\right)\sum_{i=0}^k \left(\begin{matrix}k\\i\end{matrix}\right) (-1)^{k-i} i^m\\
&=&n^m-\sum_{k=0}^{n-1}\sum_{i=0}^k \left(\begin{matrix}n\\k\end{matrix}\right)\left(\begin{matrix}k\\i\end{matrix}\right) (-1)^{k-i} i^m\\
&=&n^m-\sum_{i=0}^{n-1}\sum_{k=i}^{n-1} \left(\begin{matrix}n\\k\end{matrix}\right)\left(\begin{matrix}k\\i\end{matrix}\right) (-1)^{k-i} i^m\\
\end{eqnarray}

\begin{eqnarray}
\left(\begin{matrix}n\\k\end{matrix}\right)\left(\begin{matrix}k\\i\end{matrix}\right)&=&\frac{n!}{k!(n-k)!}\frac{k!}{i!(k-i)!}\\
&=&\frac{n!}{(n-k)!}\frac{1}{i!(k-i)!}\\
&=&\frac{n!}{i!}\frac{1}{(n-k)!(k-i)!}\\
&=&\frac{n!}{i!(n-i)!}\frac{(n-i)!}{(n-k)!(k-i)!}\\
&=&\left(\begin{matrix}n\\i\end{matrix}\right)\frac{(n-i)!}{(n-k)!(k-i)!}\\
\end{eqnarray}

\begin{eqnarray}
S(m,n)&=&n^m-\sum_{i=0}^{n-1}\sum_{k=i}^{n-1} \left(\begin{matrix}n\\k\end{matrix}\right)\left(\begin{matrix}k\\i\end{matrix}\right) (-1)^{k-i} i^m\\
&=&n^m-\sum_{i=0}^{n-1}\sum_{k=i}^{n-1} \left(\begin{matrix}n\\i\end{matrix}\right)\frac{(n-i)!}{(n-k)!(k-i)!} (-1)^{k-i} i^m\\
&=&n^m-\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m\sum_{k=i}^{n-1} \frac{(n-i)!}{(n-k)!(k-i)!} (-1)^{k-i}\\
\end{eqnarray}

\begin{eqnarray}
\sum_{k=i}^{n-1} \frac{(n-i)!}{(n-k)!(k-i)!} (-1)^{k-i}&=&\sum_{k-i=0}^{n-i-1} \frac{(n-i)!}{(n-i-(k-i))!(k-i)!} (-1)^{k-i}\\
&=&\sum_{j=0}^{n-i-1} \frac{(n-i)!}{(n-i-j)!j!} (-1)^{j}\\
&=&\sum_{j=0}^{n-i-1} \left(\begin{matrix}n-i\\j\end{matrix}\right) (-1)^{j}\\
&=&-\left(\begin{matrix}n-i\\n-i\end{matrix}\right) (-1)^{n-i} + \sum_{j=0}^{n-i} \left(\begin{matrix}n-i\\j\end{matrix}\right) (-1)^{j}\\
&=&-(-1)^{n-i}+0^{n-i}
\end{eqnarray}

\begin{eqnarray}
S(m,n)&=&n^m-\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m\sum_{k=i}^{n-1} \frac{(n-i)!}{(n-k)!(k-i)!} (-1)^{k-i}\\
&=&n^m-\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m(-(-1)^{n-i}+0^{n-i})\\
&=&n^m+\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m(-1)^{n-i}-\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m 0^{n-i}\\
&=&\sum_{i=0}^{n}\left(\begin{matrix}n\\i\end{matrix}\right)i^m(-1)^{n-i}\\
&=&\sum_{k=0}^n \left(\begin{matrix}n\\k\end{matrix}\right) (-1)^{n-k} k^m
\end{eqnarray}
ちなみに、スターリング数はS(m,n)をn!で割ったものだ。