Past exam of the mathematics course of the University of Cambridge / 2025 / ia / Paper 2 / 10F (Probability)

Every reachable sequence is a restricted-growth sequence in $A_n$. Given one, the transition masses sum toand every allowed transition remains in $A_{n+1}$. Induction from $X_1=1$ therefore proves that $(X_1,\dots ,X_n)\in A_n$ almost surely.

Conditional on label $1$ still having frequency one, it is avoided at step $i+1$ with probability $(i+1/2)/(i+1)$. ConsequentlyThe 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

Multiplying transition probabilities along a path gives a denominator $n!$. The numerator factors into one product depending only on the final number of labels and, for each label, a productIt is therefore unchanged when the final label frequencies are permuted. This proves the claimed equality.

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