Expected number of cycles of permutation equals harmonic number of degree
Suppose is a natural number. Consider the uniform distribution on the symmetric group of degree . Then, the expected number of cycles in the cycle decomposition of a permutation chosen according to the uniform distribution is equal to the harmonic number of , where:
Note that , where is the Euler-Mascheroni constant, and its value is approximately (or very close to ). Also, . Thus, for large enough, can be approximated additively as and multiplicatively as .
|(equals expected number of cycles)|
|2||1.5 = 3/2||0.6931...|
|3||1.833.. = 11/6||1.0986...|
|4||2.0833.. = 25/12||1.3862...|
|5||2.2833.. = 137/60||1.6094...|