Rolling an $n$-sided die until repeat is found Problem: We are rolling an $n$-sided die. You roll until you reach a number which you have rolled previously. I need to calculate the probability $p_m$ that we have rolled $m$ times for such a repeat.
My first thought was to try some inputs. I took $n=6$. I noticed that when $m=1$, we will always get a probability of $0$, since you are only rolling one time. Also, for $m>7$, we will also have $0$, since we will never reach that case. Now, I don't get how to find a general formula for when $1<m<8$
 A: The probability of not finishing in $k$ rolls is
$$
\frac{n(n-1)\cdots(n-k+1)}{n^k}=\frac{k!}{n^k}\binom{n}{k}\tag{1}
$$
Thus, $p_k$, the probability of finishing on the $k^{\text{th}}$ roll is
$$
\frac{(k-1)!}{n^{k-1}}\binom{n}{k-1}-\frac{k!}{n^k}\binom{n}{k}
=\bbox[5px,border:2px solid #C0A000]{\frac{(k-1)!}{n^{k-1}}\binom{n-1}{k-2}}\tag{2}
$$
Another way to compute $p_k$ is the probability of not finishing in $k-1$ rolls times the probability of finishing in $k$ rolls given that we have not finished in $k-1$ rolls, which is $\frac{k-1}n$:
$$
\frac{(k-1)!}{n^{k-1}}\binom{n}{k-1}\frac{k-1}n
=\bbox[5px,border:2px solid #C0A000]{\frac{(k-1)!}{n^{k-1}}\binom{n-1}{k-2}}\tag{3}
$$
Using $(2)$ or $(3)$, we can compute the expected number of rolls until a repeat is achieved is
$$
\sum_{k=2}^{n+1}\frac{k!}{n^{k-1}}\binom{n-1}{k-2}\tag{4}
$$
For $n=6$, $(4)$ gives the expected number of rolls to be
$$
\frac{1223}{324}\doteq3.774691358\tag{5}
$$

Asymptotically, $(4)$ can be approximated by
$$
\sum_{k=2}^{n+1}\frac{k!}{n^{k-1}}\binom{n-1}{k-2}\sim\sqrt{\frac{n\pi}2}+\frac23\tag{6}
$$
with an error of approximately $\frac1{10\sqrt{n}}$.
A: for a die with $n$ sides, if you haven't already seen a duplicate, the probability of getting a repeat on the $k$th roll is
$$\frac{k-1}{n}$$
So, to get a repeat exactly on the $j$ you must first succeed at getting to the $j$th roll without any repeats, and then roll a repeat:
$$\begin{align}P(j) &= \frac{j-1}{n}\cdot\prod_{k=1}^{j-1}\left(1-\frac{k-1}{n}\right)\\
&=\frac{j-1}{n}\cdot\prod_{k=1}^{j-1}\left(\frac{n+1-k}{n}\right)\\
&=\frac{j-1}{n^j}\cdot\prod_{k=1}^{j-1}\left(n+1-k\right)\\
&=\frac{j-1}{n^j}\cdot\left(n\times(n-1)\times\cdots\times(n+3-j)\times(n+2-j)\right)\\
&=\frac{j-1}{n^j}\cdot\frac{n!}{(n+1-j)!}\\
&=\frac{n!\cdot(j-1)}{(n+1-j)!\cdot n^j}\end{align}$$
A: Hint: If you rolled $m$ times, that means the first $m-1$ must all have been different results, and the $m$th roll is one of the first $m-1$.
For example, if $m=3$, that means the first two rolls must be distinct, and then the third roll must match one of the first two. So this is $\frac{6}{6} \cdot \frac{5}{6} \cdot \frac{2}{6}$. (There is a $5/6$ chance that the second roll does not match the first. There is a $2/6$ chance that the third roll matches one of the first two).

 In general, $\frac{\frac{6!}{(7-m)!} \cdot (m-1)}{6^m}$.

A: the first roll does not matter, the second roll, since you dont want it to have the same number as the first, then the prob is $\frac{n-1}{n}$, so does for the third, forth, and so on until the $(m-1)$th roll. And for the last, because you want it to have same number, the probability is $\frac{1}{n}$. Hence, the answer is $\frac{(n-1)^{m-2}}{n^{m-1}}$.
