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

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

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

  3. (こちらは重複組合せになる)
  4. $\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}$ と一致する.