Expected number of turns needed to get K distinct color balls in n turns There is random ball generator which generates balls of K different colors. In each turn you ask the generator to generate a ball and it produces a ball of color from 1-K. 


*

*What is the probability that at exactly $n^{th}$ turn you will have balls of all 5 different colors ?

*What is the expected number of turns needed to get balls of all K colors ?


Here is my solution for the 1st question
$$
P(X = n) = \frac{\frac{1}{k}\sum_{x_1+..+x_{k-1} = n-1}\frac{(n-1)!}{x_1!x_2!..x_{k-1}!}}{(k-1)^{n-1}}
$$
First I can't prove that $P(X = n) \le 1$. Second, I can't use this to compute expected value (which has a closed form solution). I believe there is a way to solve 1st through inclusion exclusion. I would be much obliged if someone could point out the solution to me.
 A: Let $p_{n,r}$ be the probability that after $n$ rounds you have collected exactly $r$ different colours. Then we have the recursion
$$\tag1 p_{n+1,r}=\frac rK p_{n,r} + \left(1-\frac{r-1}K\right)p_{n,r-1}$$
and boundary condition
$$p_{0,r}=\begin{cases}1&\text{if }r=0\\0&\text{otherwise}.\end{cases} $$
Note that
$$ P(X=n) = \frac 1Kp_{n-1,K-1}$$
and
$$ E[X]=\sum_{n=1}^\infty nP(X=n)=\frac1K\sum_{n=0}^\infty n p_{n,K-1}.$$
It is at the same time obvious and an immediate consequence of (1) that $p_{n,0}=0$ for $n>0$. Therefore if $r=1$, (1) simplifies to 
$$ p_{1,1}=1\qquad p_{n+1,1}=\frac 1Kp_{n,1}$$
so that
$$ p_{n,1}=\begin{cases}0&\text{if }n=0,\\K^{1-n}&\text{if }n>0.\end{cases}$$
You can fight your way up to $r=K=5$ to solve this.

Here's an alternative way to compute only the expected value:
Let $E(K,p)$ be the expected number of rounds to collect all $K$ ball colours from a random ball generator that fails to produce anything with probability $1-p$ and produces one of $K$ colours (with equal probability) otherwise. We are looking for $E(K,1)$ and have the recursion
$$ E(K,p) = 1+(1-p) E(K,p) +p E(K-1,(1-1/K)p)$$
(We play one round; if it fails to produce a ball, we start all over; otherwise we start a different game to collect $K-1$ remaining colours and count a repeat of the colour just found as failure).
Hence
$$ E(K,p) = \frac1p + E(K-1,(1-1/K)p)$$
and by unroling this recursion with boundary condition $E(0,p)=0$
$$ E(K,1) = 1+\frac1{1-1/K}+\frac1{(1-1/K)(1-2/K)}+\ldots + \frac1{(1-1/K)(1-2/K)\cdots(1-(K-1)/K)}\\= 1+\frac K{K-1} +\frac{K^2}{(K-1)(K-2)}+\ldots +\frac{K^{K-1}}{(K-1)!}\\=\sum_{r=0}^K\frac{K^{K-r}r!}{K!}$$
