資源配分(配分先に区別が無い場合)の数$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}$

    通り