Long cycles in a random permutation
Let be the number of cycles longer than (i.e. of length ) in a uniformly random permutation of . Compute . The limit has the form for a rational ; find .
Show hints (2)+
- The expected number of cycles of a given length in a random permutation is . Sum over .
- That sum is , which tends to .
Answer
Reveal answer →Final answer
2
Want the full step-by-step worked solution? It's part of Premium - along with a worked solution for every question in the bank.
Asked at: Jane Street, Two Sigma