組み合わせの一般化。

$N$ 個の要素（例えば番号の振られたボール）のうち $r$ 個を取り出して、それを $M$ 個のグループ（例えば番号の振られた筒）に分けたときに、各グループ内の要素の個数が $n_1, \cdots, n_M$ となる組み合わせの数は、
$\displaystyle \frac{ N! }{ n_1! n_2! \cdots n_M! (N-r)! }$
ただし
$\displaystyle \sum^M_{i=1} n_i = r$

証明

$N$ 個の要素（例えば番号の振られたボール）から $r$ 個を取り出して並べる順列は、
$\displaystyle {}_NP_r = \frac{ N ! }{ ( N - r )! }$
で与えられる。

この順列において、前から $n_1$ 個の要素をグループ1に入れ、その後ろ $n_2$ 個をグループ2に入れる。
$n_i \, (i > 2 )$ も同様のグループ分けを行うことで、全ての要素のグループ分けが完了する。

イメージとしては、透明な筒を1から順に並べておいて、 $N$ 個ボールの入った籠からランダムにボールを一個取り出しては筒1の中のボールの個数が $n_1$ になるまでボールを入れて、 $n_1$ 個になったら筒2にボールを $n_2$ 個になるまで入れていくという感じ。
ボールの方の順番が変わるため、筒の順番は固定させておかなければならない。
また、筒に入れることによって、入れたボールの順番が分かる。

欲しいのは組み合わせだから、筒の中に入ったボールにおける順列の数だけ重複が存在する。
したがって、元の順列 ${}_NP_r$ を $n_1!, n_2!, \cdots$ で割ることによって、求めるべき組み合わせの数が得られる。

nano_exit

基礎的なことこそ、簡単な例が必要だと思うのです。

組み合わせの一般化。