# Solution: 2020-15 The number of cycles of fixed lengths in random permutations

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.

GD Star Rating