# Enumerating all permutations that are "square roots" of derangements

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.

• Your condition is equivalent to all cycles having length 3 or greater, right? Sep 27, 2019 at 17:43
• yes, but when thinking about how to formulate the question, I decided for emphasising the relation to derangements. Sep 27, 2019 at 17:49
• 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. Sep 27, 2019 at 17:52
• @SamHopkins thanks for providing that information; I guess that will solve my problem. Sep 27, 2019 at 18:00
• 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. Sep 27, 2019 at 18:23

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