How Many Cycles Does a Random Permutation Have? (Part 1)
Published:
A few days ago, I was doom-scrolling on Instagram and came across a post that shared an interview problem of a quant firm: “Let $C_n$ denote the number of cycles in a random permutation of $[2n] = \{1,2,\ldots,2n\}$ whose lengths are greater than $n$. What is $\lim_{n \to \infty} \mathbb{E}[C_n]$?”. It caught my attention almost immediately, since permutation problems were among my favorites back when I did competitive programming. “This should be quite easy for me,” I said to myself, and started doing some calculations. Oh boy. It opened up a whole rabbit hole, leading me to a bunch of related questions, and a few interesting findings of my own, that ended up consuming most of my weekend.