資源配分の数$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−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}

と計算できる．

資源配分の計算練習

次の値を求めよ．

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

  1. $\text{resource}(5,2)=\ _{4}\mathrm{C}_{1}=\boldsymbol{4}$
  2. $\text{resource}(7,6)=\ _{6}\mathrm{C}_{5}=\ _{6}\mathrm{C}_{1}=\boldsymbol{6}$
  3. $\text{resource}(10,4)=\ _{9}\mathrm{C}_{3}=\dfrac{9\cdot 8\cdot 7}{3\cdot 2\cdot 1}=\boldsymbol{84}$
  4. \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個はアメをもらう場合，何通り分け方があるか．
  2. 1個もアメをもらえない子供がいてもよい場合，何通りの分け方があるか．

  1. 8個のアメを8個の白丸

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

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

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

    $_{3}\mathrm{H}_{8}=\boldsymbol{45}$ 通り

資源配分〜その2〜

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

  1. 15という数を15個の白丸

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

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

    3. $\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}$ と一致する．