スターリング数の組み合わせ解釈

by nomura · 2024年5月9日

スターリング数の組み合わせ解釈
スターリング数は組み合わせ解釈をすることができる。

(1)第1種スターリング数

第1種スターリング数\(S_{1}\left(n,k\right)\)の絶対値は区別の出来る\(n\)個の玉を区別の出来ない\(k\)個の箱に巡回列として空箱なしで入れる場合の数に等しい。

(2)第2種スターリング数

第2種スターリング数\(S_{2}\left(n,k\right)\)は区別の出来る\(n\)個の玉を区別の出来ない\(k\)個の箱に空箱なしで入れる場合の数に等しい。

\(n\)人を\(k\)個の空グループなしの名前なしグループ分けするときの総数は第2種スターリング数となります。

-

\(S_{1}\left(4,2\right)\)の例
\(\left\{ a,b,c,d\right\} \)を2つの区別の出来ない箱に入れ巡回列に空箱なしで分けるには、
\(\left\{ \left(a\right),\left(b,c,d\right)\right\} \)
\(\left\{ \left(a\right),\left(b,d,c\right)\right\} \)
\(\left\{ \left(b\right),\left(a,c,d\right)\right\} \)
\(\left\{ \left(b\right),\left(a,d,c\right)\right\} \)
\(\left\{ \left(c\right),\left(a,b,d\right)\right\} \)
\(\left\{ \left(c\right),\left(a,d,b\right)\right\} \)
\(\left\{ \left(d\right),\left(a,b,c\right)\right\} \)
\(\left\{ \left(d\right),\left(a,c,b\right)\right\} \)
\(\left\{ \left(a,b\right),\left(c,d\right)\right\} \)
\(\left\{ \left(a,c\right),\left(b,d\right)\right\} \)
\(\left\{ \left(a,d\right),\left(b,c\right)\right\} \)
の11通りとなる。巡回列なので\(\left(a,b,c\right)\)と\(\left(b,c,a\right)\)は同じとなる。
これより、\(\left|S_{!}\left(4,2\right)\right|=11\)となる。

-

\(S_{2}\left(4,2\right)\)の例
\(\left\{ a,b,c,d\right\} \)を2つの区別出来ない箱に空箱なしで分けるには、
\(\left\{ \left\{ a\right\} ,\left\{ b,c,d\right\} \right\} \)
\(\left\{ \left\{ b\right\} ,\left\{ a,c,d\right\} \right\} \)
\(\left\{ \left\{ c\right\} ,\left\{ a,b,d\right\} \right\} \)
\(\left\{ \left\{ d\right\} ,\left\{ a,b,c\right\} \right\} \)
\(\left\{ \left\{ a,b\right\} ,\left\{ c,d\right\} \right\} \)
\(\left\{ \left\{ a,c\right\} ,\left\{ b,d\right\} \right\} \)
\(\left\{ \left\{ a,d\right\} ,\left\{ b,c\right\} \right\} \)
の7通りとなる。
これより、\(S_{2}\left(4,2\right)=7\)となる。

(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)\)となり題意は成り立つ。