Expected number of cycles in permutation

Question

Consider a random permutation of $1,2,\ldots,n$. What is the expected number of cycles in it? I thought about using linearity of expectation, but here it's not clear how we can break down the main random variable into different ones.

Answer 1

A simple argument shows that the expected number of fixed points (cycles of length 1) of a random permutation is $1$: Let $p_i$ be the number of permutations that fix position $i$. Clearly there are $(n-1)!$ of these. Thus all the permutations together have a total of $\sum_{i=1}^n p_i = n\cdot(n-1)!$ fixed points, and the average permutation has $\frac{n\cdot(n-1)!}{n!} = 1$ fixed points.

A generalization of this argument shows that the expected number of cycles of length $k$ is $\frac1k$.

For example, the expected number of cycles of a random permutation of order 3 is $$1 + \frac12 + \frac 13 = \frac{11}6$$

and you can easily verify this by a hand count: There are $2$ permutations of type $(a\,b\,c)$ with one cycle, $3$ permutations of type $(a)(b\,c)$ with two cycles, and $1$ permutation of type $(a)(b)(c)$ with three cycles, for a total of $2\cdot 1 + 3\cdot 2 + 1\cdot 3 = 11$ cycles for all six permutations.

The numerators are closely related to the Stirling numbers of the first kind.

Answer 2

The combinatorial class equation of permutations with cycles marked is $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET}(\mathcal{U}\times\textsc{CYC}(\mathcal{Z})).$$ This translates to the mixed (EGF/OGF) bivariate generating function $$G(z, u) = \exp\left(u\log\frac{1}{1-z}\right).$$ Differentiate with respect to $u$ $$\frac{d}{du} G(z, u) = \exp\left(u\log\frac{1}{1-z}\right)\log\frac{1}{1-z}$$ and set $u=1$ to obtain the OGF of the expected number of cycles $$Q(z) = \exp\left(\log\frac{1}{1-z}\right)\log\frac{1}{1-z} = \frac{1}{1-z}\log\frac{1}{1-z}.$$ Extracting coefficients we finally obtain $$[z^n] Q(z) = \sum_{p=1}^n [z^p] \log\frac{1}{1-z} = \sum_{p=1}^n \frac{1}{p} = H_n.$$

Remark. Differentiating and setting $u=1$ turns $m \times u^k z^n/n!$ into $m \times k z^n/n!$ where $m$ counts the number of permutations of $n$ elements having $k$ cycles, i.e. $m=\left[n\atop k\right].$