The Expected Number of Cycles in a Permutation
An Exact Formula!
I recently came across a really interesting result that counts the expected number of cycles
in a permutation of size n.
It is really cool because I often looked at cycles in permutations, and wondered how many one
could get as n grows large. The answer may be surprising but, should make intuitive sense.
There are 2 approaches shared below - one is based on generating functions (and loosely
symmetric functions), and the other is quite elementary.
The content below contains my adaptation of a proof I read and also a different approach which is my own.
I hope you enjoyed reading this!!!
Credit: Stanley Richard. Enumerative Combinatorics. Cambridge University Press, 2012.