ボールが揃う場合の数

前回の記事中にあった問題を一般化してみました。

「n種類の異なるボールが入った袋からボールを取り出し袋に戻す操作をr回繰り返したとき、取り出したボールの種類がちょうどk種類になる場合の数はいくつか。」

一見すると簡単そうです。しかし、実は難しいのです。

n種類のボールを予め別に用意しておいて、取り出したボールと同じものを順番に1番目の箱、2番目の箱、…、r番目の箱に入れていくと考えます。
すると、それぞれの箱にはk種類あるうちのいずれか1個のボールが入っていて、全体としてはk種類のボールがある状態になります。
例えば、r個の箱全体をX={1,2,3,4}、k種類のボール全体をY={B,C,D}とすると

という感じです。

このままではまだ考えにくいので、発想を転換します。
「ボール」と「箱」という言葉を入れ替えてみてはどうでしょう。
つまり、r個の箱にk種類のボールが1個ずつ入っているのではなくて、r種類のボールがk個の箱のそれぞれに最低1個は入っているものと解釈し直すのです。
上の例で言うと、1〜4までの番号の書かれた4種類のボールが、B,C,Dの3個の箱のそれぞれに最低1個は入っている、ということになります。

したがって、問題を次のように言い換えることができます。
「r個の異なるボールをn個の異なる箱に入れる。このとき、ボールが入った箱の個数がちょうどk個になる場合の数はいくつか」

n個の箱からk個の箱を選ぶ場合の数はなので、あとは
「r個の異なるボールをk個の異なる箱に入れる場合の数」…(1)
を求めて、それにをかければヨロシ。

(1)は、次のように表されます。

したがって、求める場合の数は


です。