Average maximum length of a cycle in a permutation

Question

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 ?

Answer 1

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).}$$

Answer 2

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\;. $$