Some questions concerning the symmetric group $S_n$

Let $a_n$ be the number of permutations in $S_n$ having an square root.

1. Is it true that $a_{2n+1} = (2n+1)a_{2n}$ ? (experimental data's shows that this is true for small values of $n$).

2. Is there any formula expressing $a_n$ in terms of $n$?

3. Among all elements of $S_n$ which ones has the most number of square roots and what is this max value ?

Solution 1:

The sequence $a_n$ you are referring is listed in the Online Encyclopedia of Integer Sequences:

OEIS: A003483

The entry gives the following information:

1. It is indeed true that $a_{2n+1} = (2n+1)a_{2n}$.

2. There does not seem to be a closed-form formula for $a_n$, although the entry does give a closed-form formula for the exponential generating function.

3. The entry also gives an asymptotic estimate of the form $\displaystyle a_n \sim C \frac{n!}{\sqrt{n}}$, where $C$ is a certain constant.

Incidentally, observe that a permutation in $S_n$ has a square root if and only if its cycle decomposition has an even number of cycles of each even length. This follows immediately from the fact that the square of a $k$-cycle is a $k$-cycle if $k$ is odd, and is a pair of disjoint $(k/2)$-cycles if $k$ is even.

Edit: By the way, does anyone know a simple argument that $a_{2n+1} = (2n+1)a_{2n}$? This isn't obvious to me.