4
$\begingroup$

What is the number of permutations $\pi\in S_n$ that are products of disjoint cycles of distinct length? What is the number of permutations that are products of disjoint cycles such that no more than $k$ cycles are of any given length?

I am really interested in the asymptotics of the proportion of permutations in $S_n$ with these properties as $n\to \infty$. What is a good reference for this sort of statistics?

$\endgroup$
  • 1
    $\begingroup$ Dumb question (from me): you are ignoring cycles of length one (fixed points), right? In which case, a good start on estimating the size of the complement is counting all permutations with two cycles of length two, and over counting by adding those with two cycles of length three. For back of the envelope estimates I would start with that. Gerhard "Higher Order Terms Can Wait" Paseman, 2018.11.02. $\endgroup$ – Gerhard Paseman Nov 2 '18 at 17:41
  • $\begingroup$ Actually, both versions of the question interest me - ignoring fixed points and considering them as cycles of length 1. $\endgroup$ – H A Helfgott Nov 2 '18 at 18:52
9
$\begingroup$

If we denote by $c_i(\sigma)$ the number of cycles of length $i$ in $\sigma$, we can write the exponential generating function of permutations with cycle statistics as $$\sum_{n\geq 1}\sum_{\sigma\in S_n}\left(\frac{x^n}{n!}\prod_{i\geq 1}t_i^{c_i(\sigma)}\right)=\exp\left(\sum_{i\geq 1} \frac{t_ix^i}{i}\right) =\prod_{i\geq 1} \left(1+\frac{t_ix^i}{i}+\frac{t_i^2x^{2i}}{2i^2}+\cdots\right)$$ From here we see that the exponential generating function of permutations with distinct cycle sizes can be obtained by removing all terms where any $t_i$ has exponent $\geq 2$, and then setting all $t_i=1$. So we get $$\prod_{i\geq 1}\left(1+\frac{x^i}{i}\right)$$ From here the methods of A Hybrid of Darboux's Method and Singularity Analysis in Combinatorial Asymptotics by P. Flajolet, E. Fusy, X. Gourdon, D. Panario, N. Pouyanne show that the coefficient of $x^n$ is asymptotically equal to $$e^{-\gamma}+\frac{e^{-\gamma}}{n}+O\left(\frac{\log n}{n^2}\right)$$ which means that our desired number of permutations is asymptotically given by $$n!\left(e^{-\gamma}+\frac{e^{-\gamma}}{n}+O\left(\frac{\log n}{n^2}\right)\right).$$ Notice that in section 3 they actually provide much more refined asymptotics, in case you wanted more terms. Moreover, I believe their method should let you compute the asymptotics for permutations where no more than $k$ cycles are of any given length. In this case the generating function is given by $$\prod_{i\geq 1}\left(1+\frac{x^i}{i}+\frac{x^{2i}}{2i^2}+\cdots +\frac{x^{ki}}{k!i^k}\right)$$ from the same considerations as above.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.