資源配分(配分先に区別が無い場合)

資源配分では、ボールと箱のモデルで「区別しないn個のボールを、区別するr個の箱に最低1個は配る場合の数」を扱った。『資源配分』の問題において、同じ種類の袋に配分するなどの理由で、配分先を区別する必要がない場合も考えられる。ここでは、配分先を区別しない場合の資源配分、すなわち箱を区別しない場合のボールの配分について考えてみよう。

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

資源配分(配分先に区別が無い場合)の数

ボールと箱のモデル8

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

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

を求めてみよう.

説明文
説明文

箱に区別はないが,数を数えやすくするため,とりあえず区別して考えていく.つまり,箱に区別のある 普通の資源配分に一度戻して考えていく.

ボールは区別しないので,それを $\bigcirc,\bigcirc,\bigcirc,\bigcirc,\bigcirc$ とし,箱はとりあえず区別するので番号をつけ,それを としておく.

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

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

説明文
説明文

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

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

この4つの“すきま”から2つ選んで,その2ヶ所に“しきり” $\mid$ を入れ,5個のボールを3つの 部分に分ける.図は左から1番目と3番目の“すきま”を選んで“しきり”を入れた例である.

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

に入れるボールの個数に対応させる(図参照). このように考えると

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

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

説明文
説明文

この6通りは,箱に区別がある場合の資源配分の数であるから,袋に区別が無いときには(3通りを一束にして数えるので), 図の2通りの場合だけしかない.

資源配分(配分先に区別が無い場合)の数 $p(n,r)$ の定義

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

この例では, $p(5,3)=\dfrac{6}{3}=2$ である.

資源配分(配分先に区別が無い場合)の数$p(n,r)$の計算

(無題)

区別しない $n$ 個のボールを,区別しない $r$ 個の箱に最低1個は配る場合の数 $p(n,r)$ の一般的な議論は難しいので,簡単な例題についてだけ以下に触れる.

資源配分(配分先に区別が無い場合)の計算練習

次の値を求めよ.

  1. $p(5,1)$
  2. $p(5,2)$
  3. $p(5,3)$
  4. $p(5,4)$
  5. $p(5,5)$

  1. 求めるのは「区別しない5個のボールを,区別しない1個の箱に最低1個は配る場合の数」であり,これは次の図のような $\boldsymbol{1}$ 通りである.
  2. 求めるのは「区別しない5個のボールを,区別しない2個の箱に最低1個は配る場合の数」 であり,これは次の図のような $\boldsymbol{2}$ 通りである.
  3. 求めるのは「区別しない5個のボールを,区別しない3個の箱に最低1個は配る場合の数」 であり,これは次の図のような $\boldsymbol{2}$ 通りである.
  4. 求めるのは「区別しない5個のボールを,区別しない4個の箱に最低1個は配る場合の数」 であり,これは次の図のような $\boldsymbol{1}$ 通りである.
  5. 求めるのは「区別しない5個のボールを,区別しない5個の箱に最低1個は配る場合の数」 であり,これは次の図のような $\boldsymbol{1}$ 通りである.

資源配分 (配分先に区別が無い場合)

区別しない9個のボールを,区別しない3つの箱に配る場合について,どの箱にも最低1個はボールを配るとして,その配り方には何通りの方法があるか求めよ.

まず,ボールを区別せず,箱を区別する(a箱,b箱,c箱と名付ける) 場合について考える.

このとき,9個のボールを3つの箱に分ける方法は,並べた9個のボールの“すきま”8ヶ所に“しきり”を2ヶ所いれ,左から順にa箱,b箱,c箱に入れるボールの数と対応させればよい. つまり, $_{8}\mathrm{C}_{2}=28$ 通りある.

a箱,b箱,c箱にはいるボールの数がそれぞれ $l,m,n$ のとき, $(l,m,n)$ と表す.

  1. 28通りのうち3つの箱とも入るボールの数が等しくなるのは
  2. \begin{align} (3,3,3) \end{align}

    の1通り.

  3. a箱,b箱に入るボールの数が等しいのは,3箱とも入るボールの数が同じ場合を除くと
  4. $(1,1,7),(2,2,5),\overbrace{(3,3,3)}^\text{これは除く},(4,4,1)$

    の3通りある.3つの箱のうち,どの2つの箱に入る球の数が等しくなるかは $_{3}\mathrm{C}_{2}$ 通りあるので, 2つの箱に入るボールの数が等しいのは $_{3}\mathrm{C}_{2}\times3=9$ 通り.

  5. 3つの箱に入るボールの数がばらばらであるのは, $28−(1+9)=18$ 通り.
  6. よって,箱の区別をなくすと

    $1+\dfrac{9}{3}+\dfrac{18}{3!}=\boldsymbol{7}$ 通り

    $\uparrow\ p(9,3)$

7通りの内訳は次のようになる.

★資源配分 (配分先に区別が無い場合)

$n$ を正の整数とし, $n$ 個のボールを3つの箱に分けて入れる問題を考える.ただし,1個のボールも入らない箱があってもよいものとする.

  1. 互いに区別のつかないボールを,A,B,Cと区別された3つの箱に入れる場合,その入れ方は全部で何通りあるか.
  2. $n$ が6の倍数 $6m$ ( $m$ は自然数)であるとき, $n$ 個の互いに区別のつかないボールを,区別のつかない3つの箱に入れる場合,その入れ方は全部で何通りあるか. $m$ を用いて表せ.

  1. Aに $a$ 個,Bに $b$ 個,Cに $c$ 個入れるとして
  2. $a+b+c=n$ を満たす0以上の整数の組 $(a,b,c)$ が何組あるかと対応する.

    $\uparrow$ 資料配分〜その2〜の例題を参照のこと

    よって

    \begin{align} _{3}\mathrm{C}_{n}=&\ _{n+2}\mathrm{C}_{n}=\ _{n+2}\mathrm{C}_{2}\\ =&\boldsymbol{\dfrac{(n+2)(n+1)}{2}}通り \end{align}

  3. 1. の $\dfrac{(n+2)(n+1)}{2}$ 通りのうち
    1. 3箱に入るボールの数がすべて違うものが $p$ 通り
    2. 3箱に入るボールの数が2箱については同じものが $q$ 通り
    3. 3箱に入るボールの数がすべて同じものが $r$ 通り

    あるとすれば,求める値は,箱の区別を無くすため,それぞれ6,3,1で割って $\dfrac{p}{3!}+\dfrac{q}{3}+r$ 通りとなる.

    まず, $r$ は明らかに1である.

    次に, $q$ を求める.どの2つの箱に入るボールの数が等しくなるかで $_{3}\mathrm{C}_{2}$ 通りある. 例えば $a$ と $b$ が等しい場合

    \begin{align} (a,b,c)=&(k,k,6m-2k)\\ &\qquad(k=0,1,\cdots,3m) \end{align}

    なので, $3m+1$ 通りあるが,3箱に入るボールの数がすべて同じになる場合である $(a,b,c)=(2m.2m,2m)$ の1通りを引いて,

    $3m$ 通りある.よって

    \begin{align} q=\ _{3}\mathrm{C}_{2}\cdot3m=9m \end{align}

    最後に, $p$ は全体から $q,r$ を引くことにより求まり

    \begin{align} p=&\ \frac{(n+2)(n+1)}{2}-9m-1\\ =&\ \frac{(6m+2)(6m+1)}{2}-9m-1\\ =&\ 18m^2 \end{align}

    以上より

    $\dfrac{18m^2}{3!}+\dfrac{9m}{3}+1=\boldsymbol{3m^2+3m+1}$

    通り

資源配分(配分先に区別が無い場合)の和

資源配分(配分先に区別が無い場合)の和

資源配分 (配分先に区別が無い場合)の例題において. 空の箱があってもよいとすると,何通りの配り方があるか求めよ.

資源配分 (配分先に区別が無い場合)の解答より,

空の箱が1つも無い場合には7通りであった.

2つの箱が空箱になるのは,1通り. 1つの箱が空箱になるのは(数えて)4通り.よって

$1+4+7=\boldsymbol{12}$ 通り

$\uparrow p(9,1)+p(9,2)+p(9,3)$

この例題からわかるように,空の箱があってもよい場合のボール の配り方は, $p(n,r)$ の和となる. ボールと箱のモデルでまとめると,次のようになる.

資源配分(配分先に区別が無い場合)の和

「区別しない $n$ 個のボールを,区別しない $r$ 個の箱に配る(何個でもよい)場合の数」は, $p(n,1)+p(n,2)+\cdots+p(n,r)$ と表すことができる.

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

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

数の分割

自然数の5を正の整数の和(5そのものも含むとする)として表す方法には,和の順番を区別しなければ

\begin{align} &5,4+1,3+2,3+1+1,2+2+1,\\ &\qquad2+1+1+1,1+1+1+1+1 \end{align}

の7通りある.

このように,正の整数 $n$ を正の整数の和として表すことを,正の整数 $n$ の分割(partition)といい,その表し方の総数を $\text{FTEXT}$ では $p(n)$ と表す.この例から, $p(5)=7$ である.

資源配分(配分先に区別が無い場合)の計算練習の例題より

\begin{align} &p(5,1)=1,p(5,2)=2,p(5,3)=2,\\ &\qquad p(5,4)=1,p(5,5)=1 \end{align}

であったが,これらは自然数5の分割のすべてのパターンを表したものであるので

\begin{align} p(5)=&p(5,1)+p(5,2)+p(5,3)\\ &\qquad+p(5,4)+p(5,5) \end{align}

が確認できる.