# Expected number of cycles of permutation equals harmonic number of degree

## Statement

Suppose $n$ is a natural number. Consider the uniform distribution on the symmetric group of degree $n$. 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 $H_n$ of $n$, where:

$H_n := 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$

Note that $\lim_{n \to \infty} H_n - \log n = \gamma$, where $\gamma$ is the Euler-Mascheroni constant, and its value is approximately $0.577$ (or very close to $1/\sqrt{3}$). Also, $\lim_{n \to \infty} H_n/\log n = 1$. Thus, for $n$ large enough, $H_n$ can be approximated additively as $\log n$ and multiplicatively as $\log n$.

## Particular cases

$n$ $H_n$ (equals expected number of cycles) $\log n$
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...