On the lengths of the cycles of random permutations A random permutation of $n$ from $n$ is chosen. What is the mathematical expectation of the sum of squares of lengths of its cycles?
 A: Let $[n]=\{1,2,\ldots,n\}$. Let us compute the distribution of the length $\ell$ of the cycle passing by $1$ in a random permutation $s$ uniformly distributed in $\mathfrak S_n$. 
If $s(1)=1$, then $\ell=1$. This happens with probability $\frac1n$. Conditionally on $s(1)\ne1$, one can assume without loss of generality that $s(1)=2$. Then $\ell=2$ if $s(2)=1$. This happens with conditional probability $\frac1{n-1}$ since $s(2)$ can be any number in $[n]\setminus\{2\}$. Thus $\ell=2$ with unconditional probability $\left(1-\frac1n\right)\cdot\frac1{n-1}=\frac1n$. Iterating this reasoning, one sees that $\ell=i$ with probability $\frac1n$ for every $i$, that is, that $\ell$ is uniformly distributed on $[n]$.
Once the cycle passing by $1$ is determined, the rest of $s$ is a permutation on the complement of this cycle in $[n]$, that is, a permutation a set with $n-\ell$ elements.
Thus, the sum $S_n$ of the squares of the lengths of the cycles of a permutation uniformly distributed in $\mathfrak S_n$ is such that
$$
S_n\stackrel{\mathrm{dist.}}{=}\ell^2+S_{n-\ell},
$$
where $\ell$ is uniformly distributed on $[n]$, with the convention that $S_0=0$. In particular,
$$
E[S_n]=\frac1n\sum_{k=1}^n\left(k^2+E[S_{n-k}]\right)=\frac1n\sum_{k=1}^nk^2+\frac1n\sum_{k=1}^{n-1}E[S_{k}].
$$
One can solve this recursion in a elementary way, noting that
$$
nE[S_n]=\sum_{k=1}^nk^2+\sum_{k=1}^{n-1}E[S_{k}],
$$
hence
$$
nE[S_n]-(n-1)E[S_{n-1}]=n^2+E[S_{n-1}],
$$
that is,
$$
E[S_n]=n+E[S_{n-1}],
$$
and finally,
$$
E[S_n]=\sum_{k=1}^nk=\frac{n(n+1)}2.
$$
A: The exponential generating function of permutations by the sum of the squares of the lengths of its cycles is
$$ G(z, u) = 
\exp
\left(u z + \frac{1}{2} u^4 z^2 + \frac{1}{3} u^9 z^3 + \frac{1}{4} u^{16} z^4 \cdots\right)$$
which means that the probability generating function of the expectation that we are looking for is
$$ \left.\frac{\partial}{\partial u} G(z, u) \right|_{u=1} \\= 
\left.
\exp
\left(u z + \frac{1}{2} u^4 z^2 + \frac{1}{3} u^9 z^3 + \frac{1}{4} u^{16} z^4 \cdots\right)
\left(z + 2 u^3 z^2 + 3 u^8 z^3 + 4 u^{15} z^4 \cdots\right)
\right|_{u=1} \\=
\exp\log\frac{1}{1-z}\times \frac{z}{(1-z)^2} = 
\frac{1}{1-z}\times \frac{z}{(1-z)^2} =
\frac{z}{(1-z)^3}.$$
The conclusion is that the expectation we are trying to compute is given by
$$[z^n]  \left.\frac{\partial}{\partial u} G(z, u) \right|_{u=1} =
[z^n] \frac{z}{(1-z)^3} = \frac{1}{2} n (n+1).$$
