Processing math: 89%

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

nSr の性質を利用した計算

  1. 2以上の整数 n,r において
    2. nSr= n−1Sr−1+r× n−1Sr

    が成り立つことを， nSr の(計算ではなく)意味を考えることによって示せ．

  2. 1.を利用して， 5S3 を求めよ．

  1. nSr すなわち「区別する n 個のボールを，区別しない r 個の箱に最低1個は配る場合の数」は，

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

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

      2. n−1Sr−1 通り

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

      3. n−1Sr×r 通り

    よって

    nSr= n−1Sr−1+r× n−1Sr

    が成り立つ．

  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}