1
$\begingroup$

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.

  • 0
    The sections on Permut$a$tions in Stanley's Enumerative Combinatorics and Wil$f$'s Gener$a$ting$f$unctionology both have methods $f$or solving this type of problem. Both $a$re $a$vailable $f$reely online on their $a$uthors respective webpages.2012-09-10

2 Answers 2

2

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

2

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.