資源配分の数

ボールと箱のモデル6

では，このボールと箱のモデルを使って

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

を求めてみよう．

無題

準備として，ボールは区別しないので，それを $\bigcirc,\bigcirc,\bigcirc,\bigcirc,\bigcirc$ とし，箱は区別するので番号をつけ，それをとしておく．

次の図は，に1個，に2個，に2個のボールを配った場合を表したものである．このような，ボールの配り方をすべて書き出すと

の6通りの場合があるのがわかる．

これを，計算で求めるには次のように考えるとよい．

無題

まず，区別しない5個のボールを並べて，ボールの間にある4つの“すきま”について考える．

この4つの“すきま”から2つ選んで，その2ヶ所に“しきり” $\mid$ を入れ，5個のボールを3つの部分に分ける．

こうしておいてから，この3つの部分の左，真中，右にあるボールの個数をそれぞれ3つの箱，

に入れるボールの個数に対応させる．

このように考えると，結局

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

は，4つの“すきま”から2つの“すきま”の選び方の総数となり，組合せで計算することができる．つまり， $_{4}\mathrm{C}_{2}=\dfrac{4\cdot3}{2\cdot1}=6$ 通りと計算できる．

資源配分の数 $\text{resource}(n,r)$ の定義

「区別しないn個のボールを，区別するr個の箱に最低1個は配る場合の数」を， $FTEXT$ では $\boldsymbol{\textbf{resource}(n,r)}$ と表す．

この例では

$\begin{align} \text{resource}(5,~3)=\ _{4}\mathrm{C}_{2}=6 \end{align}$

である．

資源配分の数 $resource(n,r)$ の計算

区別しない $n$ 個のボールを，区別する $r$ 個の箱に最低1個は配る場合の総数 $\text{resource}(n,r)$ も，先程の例と同じように考えることができる．

無題

まず，区別しない $n$ 個のボールを並べて，ボールの間にある $n−1$ 個の“すきま”について考える．

この $n−1$ 個の“すきま”から $r−1$ 個選んで，その $r−1$ ヶ所に“しきり” $\mid$ を入れ， $n$ 個のボールを $r$ 個の部分に分ける．

こうしておいてから，この $r$ 個の部分を左から順に， $r$ 個の箱，

に入れるボールの個数に対応させる．

$n−1$ 個の“すきま”から選んだ $r−1$ 個の場所に“しきり”を入れることにより，下の図のようになる

このように考えると，結局

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

は， $n−1$ 個の“すきま”から $r−1$ 個の“すきま”の選び方の総数となり，組合せで計算することができ

$\begin{align} \text{resource}(n,~r)=\ _{n-1}\mathrm{C}_{r-1} \end{align}$

となる．

まとめておこう．

資源配分の数 $\text{resource}(n,r)$ の計算

資源配分の数 $\text{resource}(n,r)$ は

$\begin{align} \text{resource}(n,r)=\ _{n-1}\mathrm{C}_{r-1} \end{align}$

と計算できる．

資源配分の計算練習

次の値を求めよ．

$\text{resource}(5,2)$
$\text{resource}(7,6)$
$\text{resource}(10,4)$
$\text{resource}(20,18)$

資源配分の計算練習の解答

$\text{resource}(5,2)=\ _{4}\mathrm{C}_{1}=\boldsymbol{4}$
$\text{resource}(7,6)=\ _{6}\mathrm{C}_{5}=\ _{6}\mathrm{C}_{1}=\boldsymbol{6}$
$\text{resource}(10,4)=\ _{9}\mathrm{C}_{3}=\dfrac{9\cdot 8\cdot 7}{3\cdot 2\cdot 1}=\boldsymbol{84}$
$\begin{align} \text{resource}(20,18)=&\ _{19}\mathrm{C}_{17}=\ _{19}\mathrm{C}_{2}\\ =&\ \dfrac{19\cdot 18}{2\cdot 1}=\boldsymbol{171} \end{align}$

資源配分〜その1〜

8個の区別しないアメを3人の子供に分けるとき，次の問に答えよ．

子供は皆最低1個はアメをもらう場合，何通り分け方があるか．
1個もアメをもらえない子供がいてもよい場合，何通りの分け方があるか．

資源配分〜その1〜の解答

8個のアメを8個の白丸

$\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc$

であらわし，これによってできる7ヶ所の“すきま”から2ヶ所選んで“しきり”を入れ，3つの部分に分け，左にある $\bigcirc$ の数を1番目の子供に与えるアメの数，中央にある $\bigcirc$ の数を2番目の子供に与えるアメの数，右にある $\bigcirc$ の数を3番目の子供に与えるアメの数とすればよい．

$\uparrow$ 例えば $\bigcirc\mid\bigcirc\bigcirc\bigcirc\bigcirc\mid\bigcirc\bigcirc\bigcirc$ では，アメを子供にそれぞれ1個，4個，3個与えることに対応する

よって

$\text{resource}(8,3)=\ _{7}\mathrm{C}_{2}=\dfrac{7\cdot 6}{2\cdot 1}=\boldsymbol{21}$ 通り

(こちらは重複組合わせになる)
$\uparrow$ 重複組合せ $_{n}\mathrm{H}_{r}$ のボールと箱のモデル参照
$_{3}\mathrm{H}_{8}=\boldsymbol{45}$ 通り

資源配分〜その2〜

$x+y+z+w=15$ を満たす自然数の組 $(x,y,z,w)$ の数を求めよ．
$x+y+z+w=15$ を満たす0以上の整数の組 $(x,y,z,w)$ の数を求めよ．

資源配分〜その2〜の解答

15という数を15個の白丸

$\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc$

$\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc$

であらわし，これによってできる14ヶ所の“すきま”から3ヶ所選んで“しきり”を入れ，4つの部分に分け，一番左にある $\bigcirc$ の数を $x$ の値，左から2番目にある $\bigcirc$ の数を $y$ の値，右から2番目にある $\bigcirc$ の数を $z$ の値，一番右にある $\bigcirc$ の数を $w$ の値とすればよい．

$\uparrow$ 例えば $\bigcirc\bigcirc\bigcirc\mid\bigcirc\mid\bigcirc\bigcirc$

$\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc\mid\bigcirc\bigcirc$ では， $(x,y,z,w)=(3,1,9,2)$ 対応する

よって

$\begin{align} \text{resource}(15,4)=&\ _{14}\mathrm{C}_{3}=\frac{14\cdot13\cdot12}{3\cdot2\cdot 1}\\ =&\boldsymbol{364} 通り \end{align}$

(こちらは重複組合せになる)

$\uparrow$ 重複組合せ $_{n}\mathrm{H}_{r}$ のボールと箱のモデル参照

$_{4}\mathrm{H}_{15}=\ _{4+15-1}\mathrm{C}_{15}=\ _{18}\mathrm{C}_{3}=\boldsymbol{816}$ 通り

資源配分と重複組合せ

$\text{resource}(n,r)$ と $_{r}\mathrm{H}_{n-r}$ は等しいことを説明せよ．

資源配分と重複組合せの解答

$\text{resource}(n,r)$ の定義は，「区別しない $n$ 個のボールを，区別する $r$ 個の箱に最低1個は配る場合の数」である．

$\uparrow$ 資料配分の数 $\text{resource (n,r)}$ の定義

また， $_{r}\mathrm{H}_{n-r}$ はボールと箱のモデルでは，「区別しない $n−r$ 個のボールを，区別する $r$ 個の箱に配る(何個でもよい)場合の数」である．

$\uparrow$ 重複組合せ $_{n}\mathrm{H}_{r}$ のボールと箱のモデル

$\text{resource}(n,r)$ について考える．この「最低1個は配る」について，はじめに $r$ 個の箱に1個ずつボールを配っておき，その後残った $n−r$ 個のボールを $r$ 個の箱に配る(何個でもよい)と考えてもよく，これは， $_{r}\mathrm{H}_{n-r}$ と一致する．