(combinatorics) prove that on average, n-permutations have Hn cycles without mathematical induction. Prove that on average, n-permutations have $H_n$  cycles, where $H_n=1+1/2+1/3+...+1/n$  without mathematical induction. 
I think that on average, the number of cycles of length i (1≤i≤n) should be 1/i to prove but, I don't know how to show this. Some books proved this using an indicator function. Do I have to use that?
 A: The first step is to show that the distribution of the length of the cycle containing $1$ is uniform. Indeed, the number of permutations in which $1$ is in a cycle of length $t$ is
$$ (n-1)(n-2)\cdots(n-t+1)\cdot(n-t)! = (n-1)!. $$
Here $(n-1)(n-2)\cdots(n-t+1)$ counts the number of possible cycles containing $1$ of length $t$, and $(n-t)!$ counts the number of permutations on the remaining elements.
For a fixed permutation $\pi$, define $X_i$ (for $i \in \{1,\ldots,n\}$) to be the reciprocal of the length of the cycle containing $i$. It is not too hard to see that $\sum_{i=1}^n X_i$ is the number of cycles in $\pi$ (exercise). If $\pi$ is chosen randomly, the calculation above shows that
$$ \mathbb{E}[X_i] = \sum_{t=1}^n \frac{1}{n} \cdot \frac{1}{t} = \frac{1}{n} H_n. $$
By linearity of expectation, we deduce that
$$ \mathbb{E}\left[\sum_{i=1}^n X_i\right] = H_n. $$
A: No, you don't "HAVE" to use indicators, you GET to use indicators. It's a wonderfully nice and easy method and you should be glad whenever you can use it. And it works like a charm on this problem.
The expected number of cycles of length $i$ is equal to the number of sets of size $i$, which is $\binom ni,$ times the probability that a given set of size $i$ is permuted cyclically by a random permutation of $\{1.2,\dots,n\},$ which is $(i-1)!(n-i)!/n!.$ That is, the expected number of cycles of length $i$ is
$$\binom ni\frac{(i-1)!(n-i)!}{n!}=\frac1i$$
and so the expected number of cycles of all lengths is
$$\sum_{i=1}^n\frac1i=H_n.$$
A: One can write down the disjoint cycle representation of every permutation in $S_n$ and then tally the total number of $k$-cycles seen. For every possible $k$-cycle $\sigma$ we can count the number $N(\sigma)$ of permutations which contain $\sigma$ in its cycle representation, and then sum over all such $\sigma$. The permutations of the set $\{1,\cdots,n\}$ with $\sigma$ in its cycle representation are in bijection with the permutations of $\sigma$'s fixed points, of which there are $(n-k)!$, and so $N(\sigma)$ doesn't actually depend on $\sigma$! So, compute the number of $k$-cycles $\sigma$ in $S_n$, multiply this by $(n-k)!$ and divide by $n!$ to get the average number of $k$-cycles.
A: By way of promoting symbolic combinatorics here is the species of permutations with all cycles marked: $$\mathfrak{P}(\mathcal{U}\mathfrak{C}(\mathcal{Z})).$$
This translates to the bivariate generating function
$$G(z, u) = \exp\left(u\log\frac{1}{1-z}\right).$$
We require 
$$n! [z^n] \left.\frac{\partial}{\partial u} G(z,u)\right|_{u=1}.$$
This is
$$n! [z^n] 
\left.\exp\left(u\log\frac{1}{1-z}\right)\log\frac{1}{1-z}\right|_{u=1}$$
or $$n! [z^n] \frac{1}{1-z} \log\frac{1}{1-z} = n! \times H_n.$$
It follows that the desired average is $$H_n.$$
Remark. It is generally known that the exponential generating function produces the average on differentiation and substitution (EGF turns into OGF). I included it nonetheless to aid the reader.
