離散数学・組合せ論の問題

区別できない箱に入れるので、入れ方は 6 個の玉の集合を空でない 3 個のブロックに分ける方法と 1 対 1 に対応する。その個数は第 2 種スターリング数 $S(6,3)$ である。

方法 1（全射を数える）. 箱を一時的に区別して考えると、どの箱も空でない入れ方は 6 元集合から 3 元集合への全射の個数で、包除原理により
$$3^6-\left(\genfrac{}{}{0ex}{}{3}{1}\right)2^6+\left(\genfrac{}{}{0ex}{}{3}{2}\right)1^6=729-192+3=540.$$
箱の区別をなくすと、各入れ方が $3!=6$ 回ずつ数えられているので
$$S(6,3)=\frac{540}{6}=90.$$

方法 2（漸化式）. $S(n,k)=kS(n-1,k)+S(n-1,k-1)$ と $S(n,1)=1$, $S(n,n)=1$ を使うと
- $S(3,2)=2\cdot 1+1=3$, $S(4,2)=2\cdot 3+1=7$, $S(5,2)=2\cdot 7+1=15$
- $S(4,3)=3\cdot 1+3=6$, $S(5,3)=3\cdot 6+7=25$, $S(6,3)=3\cdot 25+15=90$

となり、同じ結果を得る。

区別できる 6 個の玉を区別できない 3 個の空でない箱に入れる方法は、6 元集合を空でない 3 個のブロックに分割する方法の数、すなわち第 2 種スターリング数 $S(6,3)$ である。全射の個数は $3^6-3\cdot 2^6+3\cdot 1^6=729-192+3=540$ で、箱の区別をなくすと $3!$ で割って $540/6=90$。検算: $S(6,3)=3S(5,3)+S(5,2)=3\cdot 25+15=90$。