Expected number of cycles in permutation 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.

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].$
