Average maximum length of a cycle in a permutation I'm looking to compute the average maximum length of cycles in a given random permutation of length n.
I know that the average cycle length is equal to n/Hn, with Hn being the n-th harmonic number, and I went through the whole proof for this fact.
However I suspect that the average maximum length is a whole different problem (but maybe I am mistaken). Is there any existing formuma for it ?
 A: We have from first principles that the number of permutations
having maximum cycle length $k$ has EGF
$$\exp\left(\sum_{q=1}^k \frac{z^q}{q}\right)
- \exp\left(\sum_{q=1}^{k-1} \frac{z^q}{q}\right).$$
This uses the combinatorial class
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\textsc{SET}(\textsc{CYC}_{\le k}(\mathcal{Z}))$$
of permutations having cycle length at most $k.$
Therefore we get for the average maximum length
$$\frac{1}{n!} + [z^n] \sum_{k=2}^n
k \left(\exp\left(\sum_{q=1}^k \frac{z^q}{q}\right)
- \exp\left(\sum_{q=1}^{k-1} \frac{z^q}{q}\right)\right)
\\ = \frac{1}{n!} + [z^n] \left( \sum_{k=2}^n
k \exp\left(\sum_{q=1}^k \frac{z^q}{q}\right)
- \sum_{k=1}^{n-1}
(k+1) \exp\left(\sum_{q=1}^{k} \frac{z^q}{q}\right) \right).$$
Merging the two sums we get
$$\frac{1}{n!} + [z^n]
\left(n \exp\left(\sum_{q=1}^n \frac{z^q}{q}\right)
- \sum_{k=2}^{n-1}
\exp\left(\sum_{q=1}^{k} \frac{z^q}{q}\right)
- 2 \exp(z)\right).$$
This is
$$\bbox[5px,border:2px solid #00A000]{
[z^n]
\left(n \exp\left(\sum_{q=1}^n \frac{z^q}{q}\right)
- \sum_{k=1}^{n-1}
\exp\left(\sum_{q=1}^{k} \frac{z^q}{q}\right)\right).}$$
This gives the sequence $A_n$
$$1,3/2,{\frac{13}{6}},{\frac{67}{24}},{\frac{137}{40}},
{\frac{2911}{720}},{\frac{23563}{5040}},{\frac{23727}{4480}},
{\frac{2149927}{362880}},{\frac{23759791}{3628800}},\ldots$$
Computing  the  total  sum  of  maximum  cycle  lengths  of  all  $n!$
permutations we obtain $n! \times A_n$
$$1, 3, 13, 67, 411, 2911, 23563,
213543, 2149927, 23759791,\ldots$$
which points us to OEIS A028418 where these
data are confirmed. The OEIS entry  includes a recurrence which can be
used for computational purposes (OEIS lists $450$ terms).
 Owing to the coefficient extractor in front we can extend the first
sum to infinity, getting
$$[z^n]
\left(n \frac{1}{1-z}   
- \sum_{k=1}^{n-1}
\exp\left(\sum_{q=1}^{k} \frac{z^q}{q}\right)\right)$$
or
$$\bbox[5px,border:2px solid #00A000]{
n - [z^n] \sum_{k=1}^{n-1}
\exp\left(\sum_{q=1}^{k} \frac{z^q}{q}\right).}$$
A: In On the number of permutations of $n$ objects with greatest cycle length $k$, S.W. Golomb and P. Gaal, p. $211$–$218$ in Probabilistic Methods in Discrete Mathematics, V. F. Kolchin et al. (eds.), the number of permutations with given greatest cycle length is calculated recursively. The result is somewhat complicated (there's a graph of it in this answer), and they don't give a closed form for the expected value $E_n$ of the greatest cycle length, but
$$
\lim_{n\to\infty}\frac{E_n}n\approx0.62432965\;.
$$ 
