$n$個のボールと，$1$から$n$までの番号がふられた$n$個の空の箱がある．また，$1$から$n$の番号が書かれた$n$枚のカードが袋の中に入っている．いま，以下の手順に従いボールを箱の中に入れていくことを考える．
手順$1$ \quad 袋からカードを$1$枚無作為に取り出して，手順$2$に進む．
手順$2$ \quad 手順$1$で取り出したカードに書かれている番号の箱が， \begin{itemize}
空ならば，そこにボールを$1$つ入れて，手順$3$へ進む．
空でなければ，カードを袋に戻さず手元に置き，手順$1$に戻る． \end{itemize}
手順$3$ \quad 手元のすべてのカードを袋に戻す．この時点で， \begin{itemize}
すべての箱にボールが入っていれば終了する．
空の箱が$1$つでもあれば，手順$1$に戻る． \end{itemize}
また，$1 \leqq k \leqq n$を満たす自然数$k$について，$k-1$個目のボールを箱に入れ終わった状態（ただし，$k=1$のときは，はじめの状態とする）の後に， \begin{itemize}
次のボール，すなわち$k$個目のボールを箱に入れるまでにちょうど$i$枚のカードを袋から取り出す確率を$P_k(i)$とし，
$i$枚のカードを袋から取り出してもまだ次のボールを箱に入れることができない確率を$Q_k(i)$とする．ただし，$Q_k(0)=1$とする． \end{itemize} このとき，以下の問いに答えよ．
(1) $n=4$のとき$P_3(1)$，$P_3(2)$，$Q_3(2)$をそれぞれ求めよ．
(2) $Q_k(i)$を$P_k(i+1)$，$P_k(i+2)$，$\cdots$，$P_k(k)$を用いて表せ．ただし，$0 \leqq i \leqq k-1$とする．
(3) $k-1$個目のボールを箱に入れてから$k$個目のボールを箱に入れるまでに袋から取り出すカードの枚数の期待値$E_k$は$Q_k(0)+Q_k(1)+\cdots +Q_k(k-1)$であることを示せ．
(4) 不等式 \[ E_k \leqq \frac{n}{n-k+1} \] が成り立つことを示せ．
(5) 不等式 \[ E_1+E_2+\cdots +E_n \leqq n+n \log n \] が成り立つことを示せ．