1 から n まで異なる番号のついた n 個のボールを、区別のつかない3つの箱に
入れる場合、その入れ方は全部で何通りあるか。

（１）
1つの箱にすべてのボールを入れる場合が1通り。

（２）
箱に A, B, C とラベルがついている場合に、
空の箱が多くとも1つしかない入れ方の数は、

3^n - 3

通りある。

箱からラベルをはがし互いに区別がつかないようにすると、
ラベルがついていたときには、異なる入れ方としてカウント
されていた 3! 通りの入れ方が 1 通りの入れ方としてカウント
されるようになる。

よって、ラベルをはがした時に、空の箱が多くとも1つしかない
入れ方の数は、

(3^n - 3) / 3! = (3^(n-1) - 1) /2

通りある。

（１）と（２）を合計して、

(3^(n-1) + 1) / 2

通りあることになる。