Expected number of tosses before you see a repeat. Suppose we roll a fair die until some face has appeared twice. For instance, we might have a run of rolls 12545 or 636. How many rolls on average would we make? What if we roll until a face has appeared three times?
I calculated the expected value for getting a repeat for a six-sided dice and I got 1223/324 (3.77 tosses). How would we generalize this to an $n$-sided dice? What about $k$-repeats?
 A: Denote by $E_r$ the expected number of additional throws when there are $r$ numbers that we have not yet seen. The $E_r$ satisfy the following recursion:
$$E_0=1,\quad E_r=1+{r\over6} E_{r-1}\ .$$
(The next throw shows with probability ${r\over6}$ a new number instead of one we have already seen.) 
Probably there is a closed formula for the $E_r$. At any rate, doing the recursion manually gives
$$E_6={1223\over324}\doteq 3.77\ .$$
A: The probability of surviving the $k^\text{th}$ roll is
$$
\frac{n-k+1}n\tag{1}
$$
Therefore, the probability of surviving the first $k$ rolls is
$$
P_n(k)=\frac{n!}{n^k(n-k)!}\tag{2}
$$
The probability of stopping on roll $k$ is
$$
P_n(k-1)-P_n(k)\tag{3}
$$
and the expected duration is
$$
\begin{align}
E(n)
&=\sum_{k=1}^\infty k(P_n(k-1)-P_n(k))\\
&=\sum_{k=0}^\infty(k+1)P_n(k)-\sum_{k=1}^\infty kP_n(k)\\
&=\sum_{k=0}^\infty(k+1)P_n(k)-\sum_{k=0}^\infty kP_n(k)\\
&=\sum_{k=0}^\infty P_n(k)\\
&=\sum_{k=0}^n\frac{n!}{n^k(n-k)!}\\
&=\frac{n!}{n^n}\sum_{k=0}^n\frac{n^k}{k!}\tag{4}
\end{align}
$$
As shown in this answer,
$$
\sum_{k=0}^n\frac{n^k}{k!}=\frac12e^n\left(1+\frac43\frac1{\sqrt{2\pi n}}+O\left(n^{-3/2}\right)\right)\tag{5}
$$
Therefore, combining $(4)$, $(5)$, and Stirling's Formula yields
$$
\begin{align}
E(n)
&=\frac12e^n\frac{n!}{n^n}\left(1+\frac43\frac1{\sqrt{2\pi n}}+O\left(n^{-3/2}\right)\right)\\
&=\sqrt{\frac{\pi n}{2}}\left(1+\frac43\frac1{\sqrt{2\pi n}}+O\left(n^{-1}\right)\right)\\
&=\sqrt{\frac{\pi n}{2}}+\frac23+O\left(n^{-1/2}\right)\tag{6}
\end{align}
$$
Extending the argument in the answer cited for $(5)$, we get
$$
E(n)\in\left[\sqrt{\frac{\pi n}{2}}+\frac23,\sqrt{\frac{\pi n}{2}}+\frac23+\sqrt{\frac{\pi}{288n}}\right]\tag{7}
$$
A: Start with $n$-sided fair die and take $k=2$ (i.e. waiting till
a face shows up twice). 
For $i=0,1,\ldots,n$ look at the situation in which exactly $i$
faces have not shown up yet, and denote the expectation of the number
of rolls yet to come by $\mu_{n,i}$. Then we have the relation: 

$\mu_{n,i}=\frac{n-i}{n}\times1+\frac{i}{n}\times\left(1+\mu_{n,i-1}\right)=1+\frac{i}{n}\mu_{n,i-1}$
  for $i=1,\ldots,n$. 

Here $\mu_{n,0}=1$ and you are looking for $\mu_{n,n}$. 
Based on this relation it is easy to show that: 

$\mu_{n,i}=\frac{i!}{n^{i}}\times\sum_{j=0}^{i}\frac{n^{j}}{j!}$

So we have:

$\mu_{n,n}=\frac{n!}{n^{n}}\times\sum_{j=0}^{n}\frac{n^{j}}{j!}$

A: The expected number of rolls until the first $k$-repetition with an $n$-sided die is given
by the integral
$$\mathbb{E}(T)     = \int_0^\infty   \left(\sum_{j=0}^{k-1} {1\over j!}\left({x\over  n}\right)^j\right)^n \,e^{-x}\,dx. $$
In my answers to the questions below I explain why. 
How many expected people needed until 3 share a birthday?
Variance of time to find first duplicate
