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.
$\begingroup$
$\endgroup$
7
asked Sep 27, 2019 at 17:39
-
1$\begingroup$ Your condition is equivalent to all cycles having length 3 or greater, right? $\endgroup$– Sam HopkinsSep 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$– Manfred WeisSep 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$– Sam HopkinsSep 27, 2019 at 17:52
-
$\begingroup$ @SamHopkins thanks for providing that information; I guess that will solve my problem. $\endgroup$– Manfred WeisSep 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$– Brian HopkinsSep 27, 2019 at 18:23
|
Show 2 more comments
1 Answer
$\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$.
answered Sep 27, 2019 at 18:21