9
$\begingroup$

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?

1 Answers 1

9

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

  • 0
    Oops yes, the second and third were wrong and didn't fit the description. Fixed it, thanks.2012-06-18