(1)

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

(2)

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