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