スターリング数の組み合わせ解釈
スターリング数の組み合わせ解釈
スターリング数は組み合わせ解釈をすることができる。
スターリング数は組み合わせ解釈をすることができる。
(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)\)となり題意は成り立つ。
ページ情報
タイトル | スターリング数の組み合わせ解釈 |
URL | https://www.nomuramath.com/v8m2soer/ |
SNSボタン |
スターリング数の母関数
\[
\sum_{n=0}^{\infty}S_{1}\left(n,k\right)\frac{x^{n}}{n!}=\frac{\log^{k}\left(1+x\right)}{k!}
\]
スターリング数の解釈
\[
\left(-1\right)^{n+k}S_{1}\left(n,k\right)=\sum_{1\leq a_{1}<a_{2}<\cdots<a_{n-k}\leq n-1}\prod_{j=1}^{n-k}a_{j}
\]
(*)スターリング数と2項係数
\[
C\left(k,m\right)S_{1}\left(n,k\right)=\sum_{j=k-m}^{n-m}C\left(n,j\right)S_{1}\left(n-j,m\right)S_{1}\left(j,k-m\right),m\leq k
\]
スターリング数の簡単な値
\[
S_{1}\left(0,k\right)=\delta_{0k}
\]