<s>[INST] Probability: Permutations 
Consider the experiment of picking a random permutation $\pi$ on $\{1,2,...,n\}$, and define the associated random variable $f(\pi)$ as the number of fixed points of $\pi$, i.e, the number of $i$ such that $f(i)=i$.

I know that a permutation of $X=\{1,2,\ldots ,n\}$ is a one-to-one function $\pi: X \rightarrow X$. Any two functions, $\pi_1, \pi_2$ can be composed and the resulting function is also a permutation. How can I find $E(F)$ and what do we know about $E(f(\pi^2))$ and $ E(f( \pi^k))$? 
 [/INST] These can be done using generating functions. First, consider $E[F].$ The exponential generating function of the set of permutations by sets of cycles where fixed points are marked is
$$ G(z, u) = \exp\left(uz - z + \log \frac{1}{1-z}\right) =
\frac{1}{1-z} \exp(uz-z).$$
Now to get $E[F]$ compute
$$ \left.\frac{d}{du} G(z, u)\right|_{u=1} =
\left. \frac{u^0 z}{1-z} \exp(uz-z) \right|_{u=1} = \frac{z}{1-z}.$$
This means that $E[F] = 1,$ there is one fixed point on average.
Let $E[F_2]$ denote the expectation of the number of fixed points in $\sigma^2$, where $\sigma$ is a random permutation. Now we need to mark both fixed points and two-cycles, since the latter turn into two fixed points under squaring. We get
$$ G(z, u) = \exp\left(uz - z + u^2 \frac{z^2}{2} -  \frac{z^2}{2}
+ \log \frac{1}{1-z}\right) =
\frac{1}{1-z} \exp\left(uz - z + u^2 \frac{z^2}{2} -  \frac{z^2}{2}\right).$$
Continuing as before, we find
$$ \left.\frac{d}{du} G(z, u)\right|_{u=1} =
\left. \frac{u^0 z+ u^1 z^2}{1-z} 
\exp\left(uz - z + u^2 \frac{z^2}{2} -  \frac{z^2}{2}\right) \right|_{u=1} =
\frac{z+z^2}{1-z}.$$
The conclusion is that $E[F_2] = 2$ for $n\ge 2$ and there are two fixed points on average.
The pattern should now be readily apparent. For every divisor $d$ of $k$ a cycle of length $d$ splits into $d$ fixed points when raised to the power $k.$ Hence we need to mark these cycles with $u^d.$ To illustrate this consider $E[F_6].$
We get
$$ G(z, u) = \exp\left(uz - z + u^2 \frac{z^2}{2} -  \frac{z^2}{2} +
u^3 \frac{z^3}{3} -  \frac{z^3}{3} + u^6 \frac{z^6}{6} -  \frac{z^6}{6} 
+ \log \frac{1}{1-z}\right) \\ =
\frac{1}{1-z} \exp\left(uz - z + u^2 \frac{z^2}{2} -  \frac{z^2}{2} +
u^3 \frac{z^3}{3} -  \frac{z^3}{3} + u^6 \frac{z^6}{6} -  \frac{z^6}{6}\right).$$
Once more continuing as before, we find
$$ \left.\frac{d}{du} G(z, u)\right|_{u=1} \\ =
\left. \frac{u^0 z+ u^1 z^2+ u^2 z^3+u^5 z^6}{1-z} 
\exp\left(uz - z + u^2 \frac{z^2}{2} -  \frac{z^2}{2} +
u^3 \frac{z^3}{3} -  \frac{z^3}{3} + u^6 \frac{z^6}{6} -  \frac{z^6}{6}\right) \right|_{u=1} =
\frac{z+z^2+z^3+z^6}{1-z}.$$
The conclusion is that $E[F_6] = 4$ for $n\ge 6$ and there are four fixed points on average.
The general procedure is
$$ G(z, u) = \exp\left(\sum_{d\mid k} 
\left(u^d \frac{z^d}{d} - \frac{z^d}{d}\right) + 
\log \frac{1}{1-z} \right)=
\frac{1}{1-z} \exp\left(\sum_{d\mid k} 
\left(u^d \frac{z^d}{d} - \frac{z^d}{d}\right)\right).$$
Once more continuing as before, we find
$$ \left.\frac{d}{du} G(z, u)\right|_{u=1} =
\left. \frac{\sum_{d\mid k} u^{d-1} z^d}{1-z} 
\exp\left(\sum_{d\mid k} 
\left(u^d \frac{z^d}{d} - \frac{z^d}{d}\right)\right) \right|_{u=1} =
\frac{\sum_{d\mid k} z^d}{1-z}.$$
We have shown that the value of $E[F_k]$ is equal to $\tau(k)$ (the number of divisors of $k$) as soon as $n\ge k.$ It starts out at $1$ for $n=1$ and increases by one every time $n$ hits a divisor of $k$ up to and including $k$ itself.
</s>