第2種スターリング数の性質
nSr の性質を利用した計算
- 2以上の整数 n,r において nSr= n−1Sr−1+r× n−1Sr
- 1.を利用して, 5S3 を求めよ.
が成り立つことを, nSr の(計算ではなく)意味を考えることによって示せ.
- nSr すなわち「区別する n 個のボールを,区別しない r 個の箱に最低1個は配る場合の数」は,
- 特定のボールが1つだけで入る箱がある
- 特定のボールが1つだけで入る箱がない
- については,まず特定のボールを1つの箱に入れておいて,残り n−1 個のボールを残りの r−1 個の箱にしまえばよいから
- については,まず特定のボール以外の n−1 個のボールを r 個の箱にしまっておいて,最後に特定のボールをすでに他のボールが 入っている r 個の箱のどれかにしまえばよいから
次の2つの場合に分けることができる.
n−1Sr−1 通り

n−1Sr×r 通り

よって
nSr= n−1Sr−1+r× n−1Srが成り立つ.
\begin{align} _5\mathrm{S}_3=&\ _4\mathrm{S}_2+3\ _4\mathrm{S}_3\\ =&\ (\ _3\mathrm{S}_1+2\ _3\mathrm{S}_2)+3(\ _3\mathrm{S}_2+3\ _3\mathrm{S}_3)\\ =&\ _3\mathrm{S}_1+9\ _3\mathrm{S}_3+5\ _3\mathrm{S}_2\\ =&\ _3\mathrm{S}_1+9\ _3\mathrm{S}_3+5(\ _2\mathrm{S}_1+2\ _2\mathrm{S}_2)\\ =&\ 1+9+5(1+2\cdot1)=\boldsymbol{25} \end{align}