# Find all permutations with a specific property

Permutation $\tau$ has only cycles with two and three elements. It has four cycles with two elements and five cycles with three elements. Find the number of all permutations $\sigma$ such that $\sigma^4=\tau$.

I completely don't know how to approach. I think decomposition of permutation into cycles is crucial but don't know how to exactly use it.

-
@RagibZaman: It can be deduced from the question (assuming that "only cycles with two and three elements" implies there can be no fixed points, which is true in the combinatorial interpetation of "cycles") that $\tau$ is a permutation of $4\times2+5\times3=23$. –  Marc van Leeuwen Sep 10 '12 at 13:49
@MarcvanLeeuwen Ah yes. I'll delete that comment then. Thanks. –  Ragib Zaman Sep 10 '12 at 13:54
The sections on Permutations in Stanley's Enumerative Combinatorics and Wilf's Generatingfunctionology both have methods for solving this type of problem. Both are available freely online on their authors respective webpages. –  Ragib Zaman Sep 10 '12 at 13:54

Here is a hint. Find all the cycle types of permutations of $23$ (i.e., all partition of $23$) such that the fourth power of a permutation of that type gives a cycle type $(3,3,3,3,3,2,2,2,2)$. Instead of looking at all partitions of $23$, you can rapidly narrow down the search for such partitions by looking at what happens to individual cycles when taking fourth powers. Once you have the list, use that the number of permutations with type a partition $\lambda=(\lambda_1,\ldots,\lambda_k)$ of $n$ is given by $$\frac{n!}{(\prod_{i=1}^k\lambda_i)(\prod_{l=1}^{\lambda_1}m_l(\lambda)!)}$$ where $m_l(\lambda)$ counts the number of parts of $\lambda$ equal to $l$. For instance for $\lambda=(8,6,3,3,3)$ (which should appear on your list) you get $$\frac{23!}{(8\times6\times3\times3\times3) (0!\times0!\times3!\times0!\times0!\times1!\times0!\times1!)} =3\,324\,590\,630\,000\,640\,000$$ different permutations.

Oops, I forgot, this will give you the number of all permutations whose fourth power is some permutation of type $(3,3,3,3,3,2,2,2,2)$. To get the number of permutations giving a specific such permutation $\tau$, divide by the total number $2308743493056000$ of such permutations. The division must be exact, which gives a nice test for errors. Maybe it is easier (and avoids large numbers better) to figure out for every $\lambda$ separately how many possibilities you have for a permutation $\sigma$ of type $\lambda$ to satisfy $\sigma^4=\tau$.

-

Marc's comment and answer are excellent, but I think it's more efficient to start with a particular $\tau$, say, $$\tau=(1\ 2)(3\ 4)(5\ 6)(7\ 8)(9\ 10\ 11)(12\ 13\ 14)(15\ 16\ 17)(18\ 19\ 20)(21\ 22\ 23)$$ and count the number of $\sigma$ with $\sigma^4=\tau$.

As Marc says, you have to determine the possible cycle structures for $\sigma$. Convince yourself that it can't have any 2- or 4-cycles; must have exactly one 8-cycle; may have 3-, 6-, and/or 12-cycles; and no other cycles are possible. Then convince yourself that the 8-cycle must be $(a\ b\ c\ d\ a'\ b'\ c'\ d')$ where the sets $\{{a,a'\}},\{{b,b'\}},\{{c,c'\}},\{{d,d'\}}$ are the sets $\{{1,2\}},\{{3,4\}},\{{5,6\}},\{{7,8\}}$ in some order --- how many possibilities are there? Then work on the 3-, 6-, and 12-cycles: what combinations are possible? and what must the individual cycles look like?

Looks like a fair bit of work.

-