Expected number of fixed points of a random permutation I am working on this problem and do not know how to proceed.
Let $X_n$ be the number of fixed points of a given permuation of $\{1,2\dots ,n\}$.
Show that for $k\in \{1,2\dots,n\}$, $E[X_n(X_n -1) \dots (X_n- k +1)] = 1$.
It is clear to me to show in the case of $k = n$, but otherwise unclear. Any pointers on how to proceed?
 A: The number of permutations of $\{1,\ldots,n\}$ for which $1,2,\ldots,r$ are all fixed points is $(n-r)!$.
Let $\sigma$ be a uniformly random permutation of $\{1,\ldots,n\}$, so $X_n$ is the number of fixed points of $\sigma$.
The probability that $1,2,\ldots,r$ are all fixed points of $\sigma$ is
$\frac{(n-r)!}{n!}$ and the same applies to any $r$-tuple $i_1,\ldots,i_r$.
Therefore if we compute the expected number of  $r$-tuples of fixed points, we obtain
$$E\Bigl[{X_n \choose r}\Bigr]={n \choose r}\cdot \frac{(n-r)!}{n!}=\frac1{r!} \,.$$
Multiplying by $r!$ gives the desired equality.
A: Using combinatorial classes as in Analytic Combinatorics by Flajolet
and Sedgewick, we have the following class $\mathcal{P}$  of permutations
with fixed points marked:
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\mathcal{P} = \textsc{SET}(
\mathcal{U} \times \textsc{CYC}_{=1}(\mathcal{Z}) +
\textsc{CYC}_{=2}(\mathcal{Z})  +
\textsc{CYC}_{=3}(\mathcal{Z})  + \cdots).$$
This gives the EGF
$$F(z, u) = \exp\left(uz+\frac{z^2}{2}
+ \frac{z^3}{3}
+ \frac{z^4}{4}
+ \cdots \right)
\\ = \exp\left(\log\frac{1}{1-z} + (u-1)z\right)
= \frac{1}{1-z} \exp\left((u-1)z\right)
\\ = \frac{1}{1-z} \exp\left(-z\right)
\exp\left(uz\right).$$
We thus obtain making use of the fact that we have an EGF
$$\mathrm{E}\left[k! \times {X_n\choose k}\right]
= [z^n] 
\left. \left(\frac{\partial}{\partial u}\right)^k F(z, u)
\right|_{u=1}
\\ = [z^n]
\left. \left(\frac{\partial}{\partial u}\right)^k
\frac{1}{1-z} \exp\left(-z\right)
\exp\left(uz\right)
\right|_{u=1}
\\ = [z^n]
\left. 
\frac{z^k}{1-z} \exp\left(-z\right)
\exp\left(uz\right)
\right|_{u=1}
\\ = [z^n] \frac{z^k}{1-z}
= [[ k\le n ]],$$
which is the claim.
