OMC260(E) の組合せ的解法
問題内容
OMC260(E) の問題文
袋の中に赤玉が $a$ 個，青玉が $b$ 個，黄玉が $c$ 個入っています．この袋に対して，黄玉を一つ取り出すまで次の操作を繰り返します．
袋の中から玉を $1$ つ取り出し，それが赤玉だった場合は袋の中に戻さず，青玉だった場合は袋の中に戻す．
このとき，操作を終了するまでに取り出した赤玉と青玉それぞれの個数の積の期待値が $1000$ となりました．
このような正整数の組 $(a,b,c)$ 全てに対して積 $abc$ を足し合わせた値を求めてください．ただし，袋の中から玉を取り出すときは，色に関係なくどの玉を取り出す確率も同様に確からしいとします．
公式解説では漸化式を使った解法でした。
解法
問題文の言い換え1
まずすべての赤玉、青玉、黄玉は同じ色でも互いに区別可能なものとします。
問題文では赤玉を引いたとき袋の中に戻さないが、これは次のように言い換えることができる。
赤玉を引いても袋の中に戻すが、同じ赤玉を2回目以降引いたときは無視することにする。
すると、「操作を終了するまでに取り出した赤玉と青玉それぞれの個数の積の期待値」は、操作を終了するまでに取り出した”無視しない赤玉”と青玉それぞれの個数の積の期待値となる。
問題文の言い換え2
「操作を終了するまでに取り出した”無視しない赤玉”と青玉それぞれの個数の積の期待値」は、「操作を終了するまでに取り出した”無視しない赤玉”と青玉の組の個数の期待値」と言い換えるとができる。
主客転倒
「操作を終了するまでに取り出した”無視しない赤玉”と青玉の組の個数の期待値」を以下のように求める
”無視しない赤玉”と青玉の組を固定してそれが現れる確率を求める。すべての”無視しない赤玉”と青玉の組について確率を合計することで求めてみる
無視しなかった赤玉が先である組の時
$x+1$回目の無視しなかった赤玉と$x+y+2$回目の青玉の組が出る確率
組を構成する”無視しない赤玉”と青玉の選び方は$ab$通りある。先に決めておく。
(i) 最初の$x$回は、袋にある$a+b+c$個の玉のうち$b$個の青玉 又は ”無視しない赤玉”として引くための一つの赤玉を除いた$a-1$個の赤玉、したがって合計$a+b-1$個を引き続けることになる。その確率は、$\Big(\dfrac{a+b-1}{a+b+c}\Big)^{x}$
(ii) x+1回目、最初に決めた無視しない赤玉を引く確率は、$\Big( \dfrac{1}{a+b+c} \Big)$
(iii) そのあとの$y$回は黄玉を引かなければ良い。その確率は$\Big( \dfrac{a+b}{a+b+c} \Big)^{y}$
(iiii) 特定の青玉を引く確率は$ \Big( \dfrac{1}{a+b+c} \Big) $
したがって 確率を合計すると
$$
\dfrac{ab}{(a+b+c)^2}\displaystyle\sum_{x=0}^{\infty} \displaystyle\sum_{y=0}^{\infty} \Big( \dfrac{a+b}{a+b+c} \Big)^{y} \Big(\dfrac{a+b-1}{a+b+c}\Big)^{x}
=\dfrac{ab}{(a+b+c)^2}\displaystyle\sum_{x=0}^{\infty} \Big(\dfrac{a+b-1}{a+b+c}\Big)^{x} \displaystyle\sum_{y=0}^{\infty} \Big( \dfrac{a+b}{a+b+c} \Big)^{y}
$$
$$
=\dfrac{ab}{(a+b+c)^2} \Big( \dfrac{a+b+c}{c+1} \Big)\Big( \dfrac{a+b+c}{c} \Big)=
\dfrac{ab}{c(c+1)}
$$
青玉が先である組の時
$x+1$回目の青玉と$x+y+2$回目の無視しない赤玉の組が出る確率
(i) (ii) (iiii) の確率は同様。組を構成する玉の選び方も同様。
(iiii) 青玉を引いて、無視しない赤玉を引く直前までの$y$回は、青玉又は無視しない赤玉として引くための赤玉を除いた$a-1$個の赤玉を引き続けると良い。その確率は$\Big( \dfrac{a+b-1}{a+b+c} \Big)^{y}$
同様にして、
$$
\dfrac{ab}{(a+b+c)^2}\displaystyle\sum_{x=0}^{\infty} \displaystyle\sum_{y=0}^{\infty} \Big( \dfrac{a+b-1}{a+b+c} \Big)^{y} \Big(\dfrac{a+b-1}{a+b+c}\Big)^{x}
=\dfrac{ab}{(a+b+c)^2}\displaystyle\sum_{x=0}^{\infty} \Big(\dfrac{a+b-1}{a+b+c}\Big)^{x} \displaystyle\sum_{y=0}^{\infty} \Big( \dfrac{a+b-1}{a+b+c} \Big)^{y}
$$
$$
=\dfrac{ab}{(a+b+c)^2} \Big( \dfrac{a+b+c}{c+1} \Big)\Big( \dfrac{a+b+c}{c+1} \Big)=
\dfrac{ab}{(c+1)^2}
$$
$a,b,c$を用いて期待値を表す
合計すると、期待値が求められる。
$\dfrac{ab}{c(c+1)}+\dfrac{ab}{(c+1)^2} =\dfrac{ab(2c+1)}{c(c+1)^2}$
この先は公式解説と全く同じです。
