(1)

求める場合の数を\(A_{1}\left(n,k\right)\)とする。
\(n-1\)個の玉の場合の数から玉を1つ追加して\(n\)個での場合の数\(A_{1}\left(n,k\right)\)を求める。
方法1は、\(n-1\)個の玉を\(k-1\)個の巡回列に分けて、k個目の巡回列に\(n\)番目の玉を1つだけ入れる方法で、場合の数は\(A_{1}\left(n-1,k-1\right)\)となる。
方法2は、\(n-1\)個の玉を\(k\)個の巡回列に分けて、\(n\)番目の玉を既に出来ている\(k\)個の巡回列に追加する方法である。
このとき\(n-1\)個の玉の中から1つ選びその玉の後に巡回列として追加すればいいので場合の数は\(\left(n-1\right)A_{1}\left(n-1,k\right)\)となる。
玉を1つ追加するには新しい箱を追加するか、既に出来ている箱に追加するしかないのでこの方法1と方法2で全てとなる。
従って漸化式は、
\begin{align*} A_{1}\left(n,k\right) & =A_{1}\left(n-1,k-1\right)+\left(n-1\right)A_{1}\left(n-1,k\right) \end{align*} となるので、\(A_{1}\left(n,k\right)=\left(-1\right)^{n+k}B_{1}\left(n,k\right)\)とおき、両辺を\(\left(-1\right)^{n+k}\)で割ると、
\[ B_{1}\left(n,k\right)=B_{1}\left(n-1,k-1\right)-\left(n-1\right)B_{1}\left(n-1,k\right) \] となり、\(B_{1}\left(n,k\right)\)は第1種スターリング数と同じ形になる。
また、1つ以上の玉を0個の箱に入れ巡回列を作るのは不可能なので0通りとなり、0個の玉を0個の箱に入れ巡回列を作る場合の数は何もしない1通りしかないので、まとめると\(A_{1}\left(0,k\right)=\delta_{0,k}\)となり、これも第1種スターリング数と同じになる。
故に初期値と漸化式が第1種スターリング数と等しいので、\(B_{1}\left(n,k\right)=S_{1}\left(n,k\right)\)となり題意は成り立つ。

(2)

求める場合の数を\(A_{2}\left(n,k\right)\)とする。
\(n-1\)個の玉の場合の数から玉を1つ追加して\(n\)個での場合の数\(A_{2}\left(n,k\right)\)を求める。
方法1は、\(n-1\)個の玉を\(k-1\)個の箱に空箱なしで分けて、k個目の箱に\(n\)番目の玉を1つだけ入れる方法で、場合の数は\(A_{2}\left(n-1,k-1\right)\)となる。
方法2は、\(n-1\)個の玉を\(k\)個の箱に空箱なしで分けて、\(n\)番目の玉を既に出来ている\(k\)個の箱に追加する方法である。
このとき、\(k\)個の中から1つ選べばいいので場合の数は\(kA_{2}\left(n,k\right)\)となる。
玉を1つ追加するには新しい箱を追加するか、既に出来ている箱に追加するしかないのでこの方法1と方法2で全てとなる。
従って漸化式は、
\begin{align*} A_{2}\left(n,k\right) & =A_{2}\left(n-1,k-1\right)+kA_{2}\left(n-1,k\right) \end{align*} となり、第2種スターリング数と同じ形になる。
また、1つ以上の玉を0個の箱に入れ巡回列を作るのは不可能なので0通りとなり、0個の玉を0個の箱に入れる場合の数は何もしない1通りしかないので、まとめると\(A_{1}\left(0,k\right)=\delta_{0,k}\)となり、これも第2種スターリング数と同じになる。
故に初期値と漸化式が第2種スターリング数と等しいので、\(A_{2}\left(n,k\right)=S_{2}\left(n,k\right)\)となり題意は成り立つ。