部屋割りの数

ボールと箱のモデル3

無題

無題

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

「区別する5個のボールを,区別する3個の箱に最低1個は配る場合の数」 を考えてみよう.

準備として,ボールは区別するので番号をつけ,それを①,②,③,④,⑤とし, 箱も区別するので番号をつけ,それを3つの箱としておく.

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

$A$ :箱1が空になる

$B$ :箱2が空になる

$C$ :箱3が空になる

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

とおくと,求めるものは $n(U)-n(A\cup{B}\cup{C})$ である.

$n(U)=3^5$ ←重複順列 $_{3}\Pi_{5}$

$n(A)=n(B)=n(C)=2^5$ ←1つ以上の箱が空になる場合

$n(A\cap{B})=n(B\cap{C})=n(C\cap{A})=1$ ←2つ(以上)の箱が空になる場合

$n(A\cap{B}\cap{C})=0$ ←全部の箱が空になる場合

であるから,包含と排除の原理を使って

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

通り となる.

ここで,ボールを箱へこのように配る方法を定義しておく.

部屋割りの数room(n,r)の定義

「区別するn個のボールを,区別するr個の箱に(空の箱がないように)最低1個は配る場合の数」を, $FTEXT$ では $\boldsymbol{room(n,~r)}$ と表す.

この例では, $room(5,~3)=150$ である.

$room(n,~r)$ は $n$ 個の要素をもつ集合 $A$ から, $r$ 個の要素をもつ集合 $B$ への全射のパターンの総数と等しい.