Let \( m_0=n \). For each \( i\geq 0 \), choose a number \( x_i \) in \( \{1,\dots, m_i\} \) uniformly at random and let \( m_{i+1}= m_i – x_i\). This gives a random vector \( \mathbf{x}=(x_1,x_2, \dots) \). For each \( 1\leq k\leq n\), let \( X_k \) be the number of occurrences of \( k \) in the vector \( \mathbf{x} \).

For each \(1\leq k\leq n\), let \(Y_k\) be the number of cycles of length \(k\) in a permutation of \( \{1,\dots, n\} \) chosen uniformly at random. Prove that \( X_k \) and \(Y_k\) have the same distribution.

The best solution was submitted by 이준호 (수리과학과 2016학번). Congratulations!

Here is his solution of problem 2020-15.