# Average length of a cycle in a n-permutation

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

• What did you try? – Ittay Weiss Aug 26 '15 at 3:13
• do you count cycles of length $1$? – Jorge Fernández Hidalgo Aug 26 '15 at 3:15

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?
• Thanks Brian! Please let me know if my further analysis is incorrect. Total number of k-cycles (in all permutations) is $n!/k$ and total number of cycles (in all permutations) is $n! \cdot H_n$. Hence, $p(length=k \mid cycle)$ (probability that a random cycle has length k) is $\frac{n!/k}{n! \cdot H_n}=\frac{1}{k \cdot H_n}$. From here, avg cycle length=$\sum_{k=1}^{n}k\cdot p(length=k | cycle)=\sum_{k=1}^{n}k\cdot \frac{1}{k\cdot H_n}=\frac{n}{H_n}$ – talegari Aug 26 '15 at 6:46
• @talegari: You're welcome! I had in mind a slightly different calculation, but yours works too. (I was calculating the total length of all cycles as $n\cdot n!$ and dividing by $n!H_n$.) – Brian M. Scott Aug 26 '15 at 7:15
• @brian-m-scott : It would be great to hear about the approach you had on mind. – talegari Aug 26 '15 at 7:17
• Proof of the fact: The expected number of k-cycles in a random permutation of $[n]$ is $\frac{1}{k}$. Let $x_i=1$ if $i$ is a part of a k-cycle, else 0. $\frac{\sum_{i=1}^{n}x_i}{k}$ counts the number of k-cycles of $[n]$. We have $E \left( \frac{\sum_{i=1}^{n}x_i}{k} \right)=\frac{1}{k} \sum_{i=1}^{n}E(x_i)=\frac{1}{k} \sum_{i=1}^{n}\frac{1}{n}=\frac{1}{k}$ Proof of the fact: Probability that 1 belongs to a k-cycle is 1/n (independent of k). Apart from one, a k-cycle can be constructed in $\binom{n-1}{k-1}(k-1)!(n-k)!$ . Dividing by $n!$ gives $\frac{1}{n}$ – talegari Aug 26 '15 at 11:21

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;

end;

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

totcyc := 0;

if n=1 then
idx := [a];
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$$