Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 9 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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