= Solution
View a restricted-growth string as a set partition. Reverse the underlying order and relabel blocks by first appearance. This is a bijection of $A_n$ which sends the size of the block containing the first position to the size of the block containing the last position. Part (c) shows that it preserves probability, so the two probabilities in part (b) are equal. Replacing $n$ there by $n+1$ gives
$$
\boxed{\mathbb E M_n=2\left(\frac{\prod_{i=1}^{n}(i+1/2)}{n!}-1\right).}
$$
Back to article page
