Solution
= Solution
Conditional on label $1$ still having frequency one, it is avoided at step $i+1$ with probability $(i+1/2)/(i+1)$. Consequently
$$
\mathbb P(N_1(X)=1)=\frac{\prod_{i=1}^{n-1}(i+1/2)}{n!}.
$$
The last observation is a singleton exactly when it introduces a new label, whose <conditional probability> is $(1+M_{n-1}/2)/n$. Taking expectations gives
$$
\boxed{\mathbb P(N_{X_n}(X)=1)=\frac{1+\tfrac12\mathbb E M_{n-1}}n.}
$$