第2種スターリング数の性質

$_{n}\mathrm{S}_{r}$ の性質を利用した計算

  1. 2以上の整数 $n,r$ において
    2. \begin{align} _n\mathrm{S}_r=\ _{n-1}\mathrm{S}_{r-1}+r\times\ _{n-1}\mathrm{S}_{r} \end{align}

    が成り立つことを， $_{n}\mathrm{S}_{r}$ の(計算ではなく)意味を考えることによって示せ．

  2. 1.を利用して， $_{5}\mathrm{S}_{3}$ を求めよ．

  1. $_{n}\mathrm{S}_{r}$ すなわち「区別する $n$ 個のボールを，区別しない $r$ 個の箱に最低1個は配る場合の数」は，

    2. 次の2つの場合に分けることができる．

    1. 特定のボールが1つだけで入る箱がある
    2. 特定のボールが1つだけで入る箱がない
    1. については，まず特定のボールを1つの箱に入れておいて，残り $n−1$ 個のボールを残りの $r−1$ 個の箱にしまえばよいから

      2. $_{n-1}\mathrm{S}_{r-1}$ 通り

    2. については，まず特定のボール以外の $n−1$ 個のボールを $r$ 個の箱にしまっておいて，最後に特定のボールをすでに他のボールが 入っている $r$ 個の箱のどれかにしまえばよいから

      3. $_{n-1}\mathrm{S}_r\times{r}$ 通り

    よって

    \begin{align} _{n}\mathrm{S}_r=\ _{n-1}\mathrm{S}_{r-1}+r\times\ _{n-1}\mathrm{S}_{r} \end{align}

    が成り立つ．

  2. \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}