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.

MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

$\begingroup$
$\endgroup$

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

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

or
Enumerative Combinatorics, v2, Example 5.2.10, which goes on to consider "$r$th roots" of the identity permutation. $\endgroup$2more comments