Expected number of cycles of permutation equals harmonic number of degree

From Groupprops
Jump to: navigation, search

Statement

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 .

See also probability distribution of number of cycles of permutation.

Particular cases

(equals expected number of cycles)
1 1 0
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...