Average length of a cycle in a n-permutation

Question

What is the average length of a cycle in a permutation of $\{1,2,3,\dots ,n\}$?

Answer 1

HINT: The expected number of $k$-cycles in a random permutation of $[n]$ is $\frac1k$. Thus, the expected number of cycles in a random permutation of $[n]$ is $\sum_{k=1}^n\frac1k=H_n$, the $n$-th harmonic number.

• How many cycles are there altogether in all permutations of $[n]$?
• What is the total length of all of these cycles?
• What is their mean length?

Answer 2

By way of enrichment here is an alternate formulation using combinatorial species. The species of permutations with cycle length marked is

$$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{U}^2\mathfrak{C}_{=2}(\mathcal{Z}) + \mathcal{U}^3\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{U}^4\mathfrak{C}_{=4}(\mathcal{Z}) + \cdots).$$

This gives the generating function $$G(z, u) = \exp\left(uz + u^2\frac{z^2}{2} + u^3\frac{z^3}{3} + u^4\frac{z^4}{4} + u^5\frac{z^5}{5} + \cdots\right)$$ which is $$G(z, u) = \exp\left(\log\frac{1}{1-uz}\right) = \frac{1}{1-uz}.$$

As this is an EGF to get the OGF of the total cycle length in all permutations we must compute $$\left.\frac{\partial}{\partial u} G(z, u)\right|_{u=1}.$$

This is $$\left. (-1) \times \frac{1}{(1-uz)^{2}} \times (-z)\right|_{u=1} = \frac{z}{(1-z)^{2}}.$$

This yields $$n! [z^n] \frac{z}{(1-z)^{2}} = n! \times n.$$

This could have been obtained trivially by noting that the cycle lengths in each permutation sum to $n$ and there are $n!$ permutations.

On the other hand the species of permutations with cycle count marked is

$$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=2}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=4}(\mathcal{Z}) + \cdots)$$

This gives the generating function $$G(z, u) = \exp\left(uz + u\frac{z^2}{2} + u\frac{z^3}{3} + u\frac{z^4}{4} + u\frac{z^5}{5} + \cdots\right)$$ which is

$$G(z, u) = \exp\left(u\log\frac{1}{1-z}\right).$$

Proceding as before to get the total number of cycles we obtain $$\left. \exp\left(u\log\frac{1}{1-z}\right) \log\frac{1}{1-z} \right|_{u=1} = \frac{1}{1-z} \log\frac{1}{1-z}.$$

This gives $$n! [z^n] \frac{1}{1-z} \log\frac{1}{1-z} = n! H_n.$$

It follows that the average is $$\frac{n}{H_n} \sim \frac{n}{\log n}.$$

The following Maple program shows how to compute this statistic using the cycle index $Z(S_n)$ of the symmetric group.

pet_cycleind_symm :=
proc(n)
local p, s;
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;


v :=
proc(n)
    option remember;
    local part, src, idx, totcyc;

    totcyc := 0; 

    if n=1 then
        idx := [a[1]];
    else
        idx := pet_cycleind_symm(n);
    fi;

    for part in idx do
        totcyc := totcyc + 
        lcoeff(part)*degree(part);
    od;

    n/totcyc;
end;

We get the sequence $$1,4/3,{\frac {18}{11}},{\frac {48}{25}},{\frac {300}{137}}, {\frac {120}{49}},{\frac {980}{363}},{\frac {2240}{761}},\ldots$$