高校数学の場合の数・確率の問題です。解答解説お願いします。

　①はたしかに $4^n - 4$ 通りとなりますね。しかし②はいささか高校で学習する範囲を超えている気がします。以下に書いたことは、私ならこう考えて解答する、という程度のことだと思って読んでください。

「$n$ 個の区別可能なボールを $m \leq n$ 個の箱へ分けて入れる仕方の数は、第2種スターリング数 $S_n^m$ として知られている。たとえば、ボール $a,b,c,d$ を $2$ 個の箱へ分けて入れる仕方は

$$a|bcd,\ b|acd,\ c|abd,\ d|abc,\ ab|cd,\ ac|bd,\ ad|bc$$

の $7$ 通りであるから、$S_4^2 = 7$ である。第2種スターリング数には

$$S_n^m = \frac{1}{m!} \sum_{k = 1}^m (-1)^{m - k} {}_m\mathrm{C}_k k^n$$

という表示が知られている（この公式の導出については、たとえば下に掲げた参考文献の第3章を参照のこと）。

　さて、$n \geq 2$ 個のボールを $4$ 個の箱へ分けて入れる仕方の数 $T_n$ を考える。ちょうど $4$ つに分けるならば $T_n = S_n^4$ であるが、空の箱があってもよいので、

$$T_n = S_n^1 + S_n^2 + \cdots + S_n^{\min(n,4)}$$

である。ここで上のスターリング数の公式から

$$T_n = 2^{n - 2} + \frac{4^{n - 1} + 2}{6}$$

となることが計算できる。ためしに計算してみると、$n = 3$ のとき $T_n = 2 + (16 + 2)/6 = 5$。一方、$3$ 個のボール $a,b,c$ を $4$ 個の箱へ入れる仕方は

$$abc|\phi|\phi|\phi,\ a|bc|\phi|\phi,\ b|ac|\phi|\phi,\ c|ab|\phi|\phi,\ a|b|c|\phi$$

の $5$ 通りであり、たしかに一致する（ここで $\phi$ は箱が空であることを表わす）。

「空の箱は $2$ 個以下」という条件を考えれば、条件に適わない $1$ 通りの場合が除外され、$2$つ以上の箱へボールを入れる仕方の数は

$$T_n - 1 = 2^{n - 2} + \frac{4^{n - 1} - 4}{6}$$

であると分かる」

参考：C.ベルジュ著 野崎昭弘訳『組合せ論の基礎』サイエンス社 サイエンスライブラリ数学=9