部屋割り（部屋に区別が無い場合）の数

ボールと箱のモデル7

説明文

説明文

ボールと箱のモデルを使って

「区別する5個のボールを，区別しない3個の箱に最低1個は配る場合の数」

を求めてみよう．

箱に区別はないが，数を数えやすくするため，とりあえず区別して考えていく．つまり，箱に区別のある 普通の部屋割りに一度戻して考えていく．

ボールは区別するので番号をつけ，それを①，②，③，④，⑤とし， 箱もとりあえず区別するので番号をつけ，それを

としておく．

集合 $A,B,C,U$ をそれぞれ

$A$ :が空になる

$B$ :が空になる

$C$ :が空になる

$U$ :ボールを適当に箱にしまう場合(空・重複有り)

とおくと，部屋割りの数は $n(U)-n(A\cup{B}\cup{C})$ である．

$n(U)=3^5$

$\uparrow$ 重複順列 $_{3}\Pi_{5}$

$n(A)=n(B)=n(C)=2^5$

$\uparrow$ 1つ以上の部屋が空になる場合

$n(A\cap{B})=n(B\cap{C})=n(C\cap{A})=1$

$\uparrow$ 2つ(以上)の箱が空になる場合

$n(A\cap{B}\cap{C})=0$

$\uparrow$ 全部の箱がからになる場合

であるから，包含と排除の原理 (3集合版)を使って

\begin{align} &\ n(U)-n(A\cup{B}\cup{C})\\ =&\ n(U)-\{n(A)+n(B)+n(C)\\ &\ -n(A\cap{B})-n(B\cap{C})-n(C\cap{A})\\ &\ \ +n(A\cap{B}\cap{C})\}\\ =&\ n(U)-n(A)-n(B)-n(C)\\ &\ +n(A\cap{B})+n(B\cap{C})+n(C\cap{A})\\ &\ \ -n(A\cap{B}\cap{C})\\ =&\ 3^5-3\cdot2^5+3-0\\ =&\ 150 \end{align}

∴150通り

となる．

説明文

説明文

以上までが，普通の部屋割りと同じ話であった．部屋に区別がない場合には，以下の点が違う．

今求めた150通りは，部屋に区別がある場合の部屋割りの数であるから，部屋に区別が無いときには，部屋を区別することによって 生じる $3!$ 通りものを1束にして数える必要がある． 例えば，図の $3!$ 通りのものは，部屋を区別しない立場では同一視しなければならない．

ここで，「区別する $n$ 個のボールを，区別しない $r$ 個の箱に最低1個は配る場合の数」を定義しておこう．

部屋割り(部屋の区別が無い場合)の数 $_{n}\mathrm{S}_{r}$ の定義

（無題）

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

この例では，$_{5}\mathrm{S}_{3}=\dfrac{150}{3!}=25$ である．

$_{n}\mathrm{S}_{r}$ の計算練習

  1. $_{2}\mathrm{S}_{1}$
  2. $_{2}\mathrm{S}_{2}$
  3. $_{3}\mathrm{S}_{1}$
  4. $_{3}\mathrm{S}_{2}$

  1. $_{2}\mathrm{S}_{1}$ は「区別する2個のボールを，区別しない1個の箱に最低1個は配る場合の数」である．これは，2個のボールを1つの箱にしまう $\boldsymbol{1}$ 通り．
  2. $_{2}\mathrm{S}_{2}$ は「区別する2個のボールを，区別しない2個の箱に最低1個は配る場合の数」 である．これは，2個のボールを2つの箱に1つずつしまう $\boldsymbol{1}$ 通り．
  3. $_{3}\mathrm{S}_{1}$ は「区別する3個のボールを，区別しない1個の箱に最低1個は配る場合の数」 である．これは，3個のボールを1つの箱にしまう $\boldsymbol{1}$ 通り．
  4. $_{3}\mathrm{S}_{2}$ は「区別する3個のボールを，区別しない2個の箱に最低1個は配る場合の数」 である．ボールを配るとき，ボールが1個の箱と2個の箱ができるが，どのボールが1個で箱に入るのかを考え， $_{3}\mathrm{C}_{1}=\boldsymbol{3}$ 通り．

部屋割り (部屋に区別が無い場合)

9人の人が，区別しない3つの部屋に泊まる場合について考える． どの部屋にも最低1人は泊まるものとすると，泊まり方には何通りの方法があるか．

まず，部屋を区別してから考える．求めるものは $_{9}\mathrm{S}_{3}$ である．

まず，3つの部屋を区別して考えていくため，部屋に $a,b,c$ と名前を付ける． 空の部屋があってもよいとした場合，各部屋への人の泊まり方は，各人に対して部屋の選び方が3通りずつあるので， $3^9$ 通り．

このうち，1部屋以上の部屋が空部屋になるのは

$_{3}\mathrm{C}_{1}\cdot2^9$ 通り

2部屋が空部屋になるのは

$_{3}\mathrm{C}_{2}\cdot1^9$ 通り

よって，空部屋が無いような人の泊まり方は

\begin{align} &3^9-\left(\ _{3}\mathrm{C}_{1}\cdot2^9-\ _{3}\mathrm{C}_{2}\cdot1^9\right)\\ =\ &3^9-3\times2^9+3通り \end{align}

本来部屋は区別しないので， $3!$ で割って

$\dfrac{3^9-3\times2^9+3}{3!}=\boldsymbol{3025}$ 通り

$\uparrow\ _{9}\mathrm{S}_{3}$

★$_nS_r$の計算

部屋を区別しない場合の，一般の部屋割りの数は $_{n}\mathrm{S}_{r}$ で表される． いま，部屋を区別する場合の部屋割りの数 $\text{room}(n,r)$ の計算において $\text{room}(n,r)$ の 部屋の区別を無くして数えたものが $_{n}\mathrm{S}_{r}$ であるから，部屋の区別によって生じる $r!$ 通りを1束として考えて

\begin{align} _n\text{S}_r=\frac{\text{room}(n,r)}{r!} \end{align}

と表される．

第2種スターリング数 $_{n}\mathrm{S}_{r}$ の計算

第2種スターリング数 $_{n}\mathrm{S}_{r}$ は

\begin{align} _n\text{S}_r=\frac{\text{room}(n,r)}{r!}=\sum_{k=0}^{r}\frac{(-1)^k(r-k)^n}{(r-k)!k!} \end{align}

と計算できる．

吹き出し無題

この計算式は理論的にはこう表せるということを示したものであり，記憶する必要は全くない． シグマ記号 $\sum$ については $\text{FTEXT}$ 数学Bを参照のこと．

第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}

部屋割り(部屋に区別が無い場合)の和

部屋割り(部屋に区別が無い場合)の和

部屋割り (部屋に区別が無い場合)の例題において， 空の部屋があってもよいとすると，何通りの方法があるか求めよ．

部屋割り(部屋に区別が無い場合)の解答より，

空部屋が無いような人の泊まり方は

$\boldsymbol{3025}$ 通り

$\uparrow\ _{9}\mathrm{S}_{3}$

だった．

2部屋が空になるのは，部屋を区別した場合には3通りあるが，部屋の区別をなくすには3で割ればよいので

$\dfrac{3}{3}=1$ 通り

1部屋が空になるのは，部屋を区別した場合には $_{3}\mathrm{C}_{1}(2^9−2)$ 通りあるが，部屋の区別をなくすには $3!$ で割ればよいので

$\dfrac{_{3}\mathrm{C}_{1}(2^9-2)}{3!}=255$ 通り

よって

$1+255+3025=\boldsymbol{3281}$ 通り

$\uparrow\ _{9}\mathrm{S}_{1}+\ _{9}\mathrm{S}_{2}+\ _{9}\mathrm{S}_{3}$

この例題からわかるように，空の部屋(箱)があってもよい場合の人(ボール)の分け方(配り方)は， $_{n}\mathrm{S}_{r}$ の和となる． ボールと箱のモデルでまとめると，次のようになる．

部屋割り(部屋に区別が無い場合)の和

「区別する $n$ 個のボールを，区別しない $r$ 個の箱に配る(何個でもよい)場合の数」は，

$\boldsymbol{_{n}\mathrm{S}_{1}}+\boldsymbol{_{n}\mathrm{S}_{2}}+\cdots+\boldsymbol{_{n}\mathrm{S}_{r}}$ と表すことができる．

（無題）

ボールと箱のモデルでの体系では以下の位置を占めている．

ボール・箱単射写像全て全射
あり・あり順列重複順列部屋割り
なし・あり組合せ重複組合せ資源配分
あり・なし（右枠の和）部屋割り（区別なし）
なし・なし（右枠の和）資源配分（区別なし）

先程の例題を少し変え，「9人の人が，区別しない9つの部屋に泊まる場合(空部屋があってもよい)何通りの泊まり方があるか」 とした場合にはその答えは

\begin{align} &_{9}\mathrm{S}_{1}+\ _{9}\mathrm{S}_{2}+\ _{9}\mathrm{S}_{3}+\ _{9}\mathrm{S}_{4}+\ _{9}\mathrm{S}_{5}\\ &\qquad+\ _{9}\mathrm{S}_{6}+\ _{9}\mathrm{S}_{7}+\ _{9}\mathrm{S}_{8}+\ _{9}\mathrm{S}_{9} \end{align}

となり，この値は $\text{B}(9)$ などと表される．