Statistical Brain Teaser - Randomized speed dating 
You and 25 strangers are in a room for 25 rounds of "speed dating." Each round, you are randomly paired with another person, regardless of whether you have seen them before or not. What is the probability that after 25 rounds, you have talked to only 1 person? 2 people? All 25 people?

The probability of talking to only 1 person is $\left(\frac{1}{25}\right)^{25} * {25 \choose 1} $, but after 2 people is where I get lost.
Running a simulation, I get about a $25\%$ chance of having talked to exactly 15 people. How do I get to this mathematically? I thought it might be
$$ \left(\frac{1}{25}\right)^{25} * (25 * 24 * 23 *...*15)  * {25 \choose 15} ,$$
however it does not get me anywhere close to $25\%$.
 A: Suppose there are $n$ other people and $r$ rounds and you want to find the probability of getting $k$ distinct matches, $1\le k\le r$. We need to partition the rounds into $k$ sets where you meet the same person in each set; the number of ways to do this is $S(r,k)$, the second-kind Stirling number. Then there are $\frac{n!}{(n-k)!}$ ways to assign people to these sets. Since there are $n^r$ possible outcomes without restrictions, the probability is
$$\frac{n!S(r,k)}{(n-k)!n^r}$$
For extremal values of $k$ the Stirling number can be simplified: $S(r,1)=S(r,r)=1$ and $S(r,2)=2^{r-1}-1$. Here $n=r=25$, whereupon the probability for $k=15$ is about $20.7\%$.
A: You can also approach this problem using states.
Let $X_0=0$, and for each $i\geq 1$, let $X_i$ denote the number of disinct people who you've seen immediately following the $i^{\text{th}}$ date. Then $\{X_i\}_{i\geq0}$ is an absorbing Markov Chain with state space $\{0,1,2,\ldots,25\}$ having transition probabilities $$P(X_{i+1}=k|X_i=k)=\frac{k}{25}$$ $$P(X_{i+1}=k+1|X_i=k)=\frac{25-k}{25}$$ You're interested in computing $P(X_{25}=k|X_0=0)$ for $k=1,2,\ldots,25$. If $P$ is your $26 \times 26$ matrix of state transition probabilities, then $$P(X_{25}=k|X_0=0)=e_1^TP^{25}e_{k+1}$$
