Is there an algorithm that enumerates all permutations that are "square roots" of derangements, i.e. permutations that, when applied twice, yield a derangement?

Other information about those kind of permutations is also welcome.

  • 1
    $\begingroup$ Your condition is equivalent to all cycles having length 3 or greater, right? $\endgroup$ Sep 27, 2019 at 17:43
  • $\begingroup$ yes, but when thinking about how to formulate the question, I decided for emphasising the relation to derangements. $\endgroup$ Sep 27, 2019 at 17:49
  • 6
    $\begingroup$ It is a classic result (attributed to Touchard?) that the generating function for the cycle index polynomials of symmetric groups is $\sum_{n \geq 0} \frac{x^n}{n!} \sum_{\sigma \in \mathfrak{S}_n} t_1^{c_1(\sigma)}t_2^{c_2(\sigma)}\cdots = e^{t_1 \frac{x}{1} + t_2\frac{x^2}{2} + t_3\frac{x^3}{3} + \cdots}$, where $c_k(\sigma)$ is the number of cycles of $\sigma$ of length $k$. Specializing $t_1=t_2=0$ and $t_3=t_4=\cdots=1$ gives the generating function for the permutations you want to count. This should easily allow you to enumerate them. $\endgroup$ Sep 27, 2019 at 17:52
  • $\begingroup$ @SamHopkins thanks for providing that information; I guess that will solve my problem. $\endgroup$ Sep 27, 2019 at 18:00
  • $\begingroup$ The cycle index polynomials that Sam mentions are also discussed in Stanley's Enumerative Combinatorics, v2, Example 5.2.10, which goes on to consider "$r$th roots" of the identity permutation. $\endgroup$ Sep 27, 2019 at 18:23

1 Answer 1


Check out "Example 2. Permutations with no small cycles" on pg. 176 of H. Wilf's "generatingfunctionology": https://www.math.upenn.edu/~wilf/DownldGF.html. It explains, using generating functions, how the number of permutations in $\mathfrak{S}_n$ you are looking for is asymptotically $\approx \frac{1}{e^{1+1/2}} n!$, just like the number of derangements is $\approx \frac{1}{e} n!$. In general the fraction of permutations with cycles all of length $>q$ is $e^{-H_q}$ where $H_q = 1+1/2+1/3+...+1/q$.


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.