n個のボールをｎ個の箱へランダムに配分するときK個の箱が空である確立

「n個のボールをｎ個の箱へランダムに配分するときK個の箱が空である確立を求めよ。ただし、ボールと箱はどちらも区別する。」という問題なんですが、解ける方がいたら、ぜひその解き方と答えを教えてください。

（ｎ－ｋ）個の箱には少なくとも１つのボールがあるので、まず、（ｎーｋ）個の箱の各々に１つずつボールをいれその後残りのｋ個のボールを配分するとして考えてみたんですが、これでは重複して数えてしまうことになり、うまく数えれませんでした。

No.1 回答者： uehashu 回答日時： 2009/05/18 07:06

適当なn(=5とか)でまず考えることをオススメします.

私の考えた解法としては,まずk=n-1から考え始めます.なお,以下の考え方では事象数を数えていますから,確率に直すときは全事象(=n^n)で割ってください.答えの事象数をQ(n)としています.

(k=n-1)
これは簡単ですね.n個の箱のうち1個にすべて入ればいいのですから,n通りです.ただし,今後の論議を簡略するために,これを(nC1)P(1)とします.ここで,nC1はnコンビネーション1,P(1)はある関数とします.この場合,P(1)=1です.
Q(1)=(nC1)P(1)

(k=n-2)
2つの箱に入る場合,まず箱を選びます.選ぶ組み合わせは(nC2)ですね.その箱にn個の玉全部が入る組み合わせは2^nです.しかし,1個の箱にしか入らない組み合わせ(2C1)P(1)通りが余分なので,引きます.
Q(2)=nC2(2^n-(2C1)P(1))

(k=n-3)
そろそろ法則が見えてきたと思います.箱を選ぶ組み合わせが(nC3)で,n個の玉全部が入る組み合わせが3^n.このとき,2個の箱にしか入らない組み合わせ(3C2)P(2)通りと1個の箱にしか入らない組み合わせ(3C1)P(1)通りが余分なので引きます.
Q(3)=(nC3){3^n-(3C2)P(2)-(3C1)P(1)}

(k=n-t)
上記の計算をまとめると,
Q(t)=(nCt){t^n-(sum_[s=1]^[t-1](tCs)P(s))}
となります.ちなみにsum_[s=1]^[t-1]は総和記号(シグマ)の開始がs=1で終了がt-1ということです(わかりづらくてすみません).
k=n-tよりt=n-kであること,P(s)を整理すること,それらを考慮して式を整理すると,うまくいきます.

この回答へのお礼

回答の手順も示していただいてありがとうございます。
とても参考になり助かりました。ありがとうございました。

お礼日時：2009/05/19 01:41