# Permutations: Given $P^4$, how many $P^1$s are possible?

Let $P^0$ be the identity tuple $(1,2,...,N)$

Let $P^{i+1}$ be the tuple after a permutation $P$ is applied to $P^i$.

For example, if $P$ is $(2,1,3,6,4,5)$ than:

\begin{align} P^0 &= (1,2,3,4,5,6) \\ P^1 &= (2,1,3,6,4,5) \\ P^2 &= (1,2,3,5,6,4) \\ P^3 &= (2,1,3,4,5,6) \\ \dots \end{align}

Given the value $P^4$, how many possible values of $P$ are there?

-

We can restate the question as: how many "fourth roots" does a given permutation have? That is, given a permutation $\sigma$, how many permutations $\tau$ exist such that $\tau^4 = \sigma$? The answer — let's call it $N(\sigma)$ — depends on the structure of $\sigma$.

(The basic idea of what to look at comes from section 4.8 of generatingfunctionology (e.g. here).)
Consider a permutation $\tau$, decomposed into cycles. For a particular cycle in $\tau$ of length $n$, let's look at what happens in $\tau^4$. If $(a_0, a_1, \dots...)$ is a cycle in $\tau$ (that is, $\tau$ takes $a_0$ to $a_1$, takes $a_1$ to $a_2$, etc.), then $\tau^4$ takes $a_0$ to $a_4$, takes $a_1$ to $a_5$, etc. The resulting (sub)permutation may be a single cycle or multiple cycles, depending upon $n$:

• If $n$ is odd (relatively prime to $4$), then we have a single cycle of length $n$, which looks like $(a_0, a_4, a_8, \dots)$ with the indices looping around modulo $n$.

• If $n$ is even but not a multiple of $4$, then we get two cycles of length $n/2$, one looking like $(a_0, a_4, a_8, \dots)$ and containing all the even indices, and the other looking like $(a_1, a_5, a_9 \dots)$ and containing all the odd ones.

• If $n$ is a multiple of $4$, then we get four cycles of length $n/4$ each, namely $(a_0, a_4, \dots)$, $(a_1, a_5, \dots)$, $(a_2, a_6, \dots)$, and $(a_3, a_7, \dots)$.

Turning this around, we can look at a cycle of length $m$ in $\tau^4$ and say the following:

• If $m$ is even, then it must have come, along with three others, as the result of a single cycle of length $4m$ splitting into four cycles of length $m$ each.

• If $m$ is odd, then either:

• One cycle of length $m$ gave rise to one cycle of length $m$,

• One cycle of length $2m$ gave rise to two cycles of length $m$ each, or

• One cycle of length $4m$ gave rise to four cycles of length $m$ each.

(This immediately gives a condition for $N(\sigma)$ to be positive, i.e. for the permutation $\sigma$ to have at least one fourth root: for every even number $m$, the number of cycles of length $m$ must be a multiple of $4$.)

We can now calculate $N(\sigma)$. For each number $m$, let the number of cycles of length $m$ in $\sigma$ be $c_m$. Then:

• If $m$ is even, then ($c_m$ must be a multiple of $4$ and) we can reconstruct a list of $c_m/4$ original cycles of length $4m$ each, by picking $c_m/4$ ordered groups of four, with ordering among them and cyclic order within each group of four being irrelevant, the number of ways of doing which is $$\frac{c_m!}{(c_m/4)!4^{c_m/4}}$$ After picking a particular group of four cycles, we can make a big one out of them (find a fourth root of the product of these four cycles) by choosing where in the cyclic ordering we start in each of the four cycles. WLOG we can fix a point in the first cycle where we start so the choice is only among the other three, so we must multiply the above number by $m^3$.

• If $m$ is odd, then for each integer partition of $c_m$ of the form $$c_m = x + 2y + 4z$$ with $x$, $y$ and $z$ being nonnegative integers, we can pick $x$ cycles of length $m$ by themselves, form $y$ pairs of cycles, and $z$ groups of four. The number of ways of doing this is $$\frac{c_m!}{x! (y!2^y) (z!4^z)}.$$ Again in each of the $y$ pairs we have $m$ ways of putting them together, and in each of the $z$ quadruplets we have $m^3$ ways of putting them together.

So using all that, the final expression for $N(\sigma)$ is:

$$N(\sigma) = \left(\prod_{2|m}\frac{c_m!m^{3c_m/4}}{(c_m/4)!4^{c_m/4}}\right) \left(\prod_{2\not|m}\sum_{x,y,z:c_m=x+2y+4z}\frac{c_m! m^y m^{3z}}{x! (y!2^y) (z!4^z)}\right)$$

I've checked this with a computer program for all permutations of size up to 12, so I'm finally convinced the expression is correct.

Examples: Consider your original permutation $\tau = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 1 & 3 & 6 & 4 & 5\end{pmatrix}$. We can write this in cycle notation as $\tau = (1 2) (3) (4 6 5)$. For this permutation, $\tau^4 = (1)(2)(3)(4 6 5)$. Notice how the cycle of length $2$ has split into two cycles of length $1$ each. If we want to start with this permutation $\sigma = (1)(2)(3)(4 6 5)$ and find fourth roots, we must look at the number of cycles $c_m$ for each $m$:

• $m = 1$: $c_m = 3$. We're looking at just the $(1)(2)(3)$ part.

• For the partition $3 = x + 2y + 4z = 1 + 2(0) + 4(0)$, we have only one ($\frac{3!}{3!} = 1$) way of picking three individual $1$-cycles: the identity permutation $(1)(2)(3)$ itself.
• For the partition $3 = x + 2y + 4z = 1 + 2(1) + 4(0)$, we have three ways ($\frac{3!}{1!2!2^1} = 3$) of picking a single $1$-cycle and a pair, corresponding to the fourth roots $(1)(2 3)$, $(2)(1 3)$ and $(3)(1 2)$ respectively.
• $m = 3$: $c_m = 1$. We're looking at the $(4 6 5)$ part.

• There's only one partition $1 = 1 + 2(0) + 4(0)$ and only one way of picking a single element out of a single one, and here the fourth root of $(4 6 5)$ happens to be $(4 6 5) itself. So the four fourth roots of$\sigma = (1)(2)(3)(4 6 5)$are •$(1)(2)(3)(4 6 5) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 2 & 3 & 6 & 4 & 5 \end{pmatrix}$, •$(1)(2 3)(4 6 5) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 1 & 3 & 2 & 6 & 4 & 5 \end{pmatrix}$, •$(2)(1 3)(4 6 5) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 2 & 1 & 6 & 4 & 5 \end{pmatrix}$, •$(3)(1 2)(4 6 5) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 1 & 3 & 6 & 4 & 5 \end{pmatrix}$. Let$\sigma = (1 2 3)(4 5 6) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 3 & 1 & 5 & 6 & 4\end{pmatrix}$. We can either choose to keep the two$3$-cycles separate ($x = 2$,$y = 0$), giving us the root$(1 2 3)(4 5 6)$itself, or we can choose to put the pair together ($x = 0, y = 1$), where the choice of the pair is unique but we can interleave the two in three ways — basically the form$(1 ? 3 ? 2 ?)$with the '?'s filled by$(4 6 5)$— giving us the roots$(1 4 3 6 2 5)$,$(1 5 3 4 2 6)$and$(1 6 3 5 2 4)$. So we have four fourth roots. Let$\sigma = (1 2)(3 4)(5 6)(7 8 9)$. In this case for$m = 2$,$c_m = 3$is not a multiple of$4$, so$N(\sigma) = 0$. Let$\sigma = \begin{pmatrix}1 & 7\end{pmatrix} \begin{pmatrix}2\end{pmatrix} \begin{pmatrix}3 & 16 & 9\end{pmatrix} \begin{pmatrix}4 & 10\end{pmatrix} \begin{pmatrix}5\end{pmatrix} \begin{pmatrix}6 & 18\end{pmatrix} \begin{pmatrix}8\end{pmatrix} \begin{pmatrix}11 & 15 & 13\end{pmatrix} \begin{pmatrix}12 & 17\end{pmatrix} \begin{pmatrix}14\end{pmatrix}$. Counting the fourth roots of this permutation by brute-force enumeration is impossible, but we can easily do it by collecting cycles of the same length: • For$m = 1$: the roots of$\begin{pmatrix}2\end{pmatrix} \begin{pmatrix}5\end{pmatrix} \begin{pmatrix}8\end{pmatrix} \begin{pmatrix}14\end{pmatrix}$are • (all separate)$\begin{pmatrix}2\end{pmatrix} \begin{pmatrix}5\end{pmatrix} \begin{pmatrix}8\end{pmatrix} \begin{pmatrix}14\end{pmatrix}$, • (two pairs)$\begin{pmatrix}2 & 5\end{pmatrix} \begin{pmatrix}8 & 14\end{pmatrix}$,$\begin{pmatrix}2 & 8\end{pmatrix} \begin{pmatrix}5 & 14\end{pmatrix}$,$\begin{pmatrix}2 & 14\end{pmatrix} \begin{pmatrix}5 & 8\end{pmatrix}$, • (all together)$\begin{pmatrix}2 & 5 & 8 & 14\end{pmatrix}$,$\begin{pmatrix}2 & 5 & 14 & 8\end{pmatrix}$,$\begin{pmatrix}2 & 8 & 5 & 14\end{pmatrix}$,$\begin{pmatrix}2 & 8 & 14 & 5\end{pmatrix}$,$\begin{pmatrix}2 & 14 & 5 & 8\end{pmatrix}$,$\begin{pmatrix}2 & 14 & 8 & 5\end{pmatrix}$. So there are$1 + 3 + 6 = 10$roots of$\begin{pmatrix}2\end{pmatrix} \begin{pmatrix}5\end{pmatrix} \begin{pmatrix}8\end{pmatrix} \begin{pmatrix}14\end{pmatrix}$. • For$m = 2$, the roots of$\begin{pmatrix}1 & 7\end{pmatrix} \begin{pmatrix}4 & 10\end{pmatrix} \begin{pmatrix}6 & 18\end{pmatrix} \begin{pmatrix}12 & 17\end{pmatrix}$are$6 \times 8 = 48$in number (pick one of the$3!$orderings of the last three, then one of the$2^3$orderings of each of the three). • For$m = 3$, the roots of$\begin{pmatrix}3 & 16 & 9\end{pmatrix} \begin{pmatrix}11 & 15 & 13\end{pmatrix}$are • (both separate)$\begin{pmatrix}3 & 16 & 9\end{pmatrix} \begin{pmatrix}11 & 15 & 13\end{pmatrix}$• (both together)$\begin{pmatrix}3 & 11 & 9 & 13 & 16 & 15\end{pmatrix}$,$\begin{pmatrix}3 & 15 & 9 & 11 & 16 & 13\end{pmatrix}$,$\begin{pmatrix}3 & 13 & 9 & 15 & 16 & 11\end{pmatrix}$. So there are$1 + 3 = 4$roots of$\begin{pmatrix}3 & 16 & 9\end{pmatrix} \begin{pmatrix}11 & 15 & 13\end{pmatrix}$. So totally$N(\sigma) = 10 \times 48 \times 4 = 1920$. - In the result for$\sigma=(123)(456)\$, I think you want (143625), (153426), and (163524). –  Gerry Myerson Jun 18 '12 at 5:48
Oops yes, the second and third were wrong and didn't fit the description. Fixed it, thanks. –  ShreevatsaR Jun 18 '12 at 6:24