Finding the number of permutations of $[12]$ of given orders

Question

Find the number of permutations of $[12]$ whose order is $a)3 \\b)4 \\c)12$

As @астонвіллаолофмэллбэрг stated in the comments, it's not an easy process and I missed counting some possible permutations already..

My solution:

a)I started choosing $3$ elements out of $12$ that are forming the order of the permutation
And WLOG, I chose $1,2,3$
So the permutations I get are:

$\begin{pmatrix} 1 & 2 & 3 & 4 & \cdots & 11 & 12 \\ \color{red}{2} & \color{red}{3} & \color{red}{1} & 4 &\cdots & 11 & 12 \end{pmatrix}$ and $\begin{pmatrix} 1 & 2 & 3 & 4 &\cdots & 11 & 12 \\ \color{red}{3} & \color{red}{1} & \color{red}{2} & 4 &\cdots & 11 & 12 \end{pmatrix}$

So, the number of permutations of $[12]$ of order $3$ is $\binom{12}3\cdot 2 $

b)Similarly, I chose $4$ elements - namely $1,2,3,4$ - out of $12$ that are forming the order of the permutation

So the permutations I get are:

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & \cdots & 11 & 12 \\ \color{red}{2} & \color{red}{3} & \color{red}{4} &\color{red}{1} & 5 & \cdots & 11 & 12 \end{pmatrix}$, $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & \cdots & 11 & 12 \\ \color{red}{2} & \color{red}{4} & \color{red}{1} &\color{red}{3} & 5 & \cdots & 11 & 12 \end{pmatrix}$, , $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & \cdots & 11 & 12 \\ \color{red}{3} & \color{red}{1} & \color{red}{4} &\color{red}{2} & 5 & \cdots & 11 & 12 \end{pmatrix}$, $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & \cdots & 11 & 12 \\ \color{red}{3} & \color{red}{4} & \color{red}{2} &\color{red}{1} & 5 & \cdots & 11 & 12 \end{pmatrix}$,

$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & \cdots & 11 & 12 \\ \color{red}{4} & \color{red}{1} & \color{red}{2} &\color{red}{3} & 5 & \cdots & 11 & 12 \end{pmatrix}$,$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & \cdots & 11 & 12 \\ \color{red}{4} & \color{red}{3} & \color{red}{1} &\color{red}{2} & 5 & \cdots & 11 & 12 \end{pmatrix}$,

So, the number of permutations of $[12]$ of order $4$ is $\binom{12}4\cdot 6 $

c) For this part I think the problem as this:

Since we want the permutation to be of order $12$, starting from $1$ :
$1$ can be matched to one of the $11$ numbers out of $12$,excluding itself, say it matched to the $2$, then there remains $10$ numbers to be matched with $2$ , exluding $1$ and itself, and there remains $9$ numbers to be matched with $3$ , exluding $1$, $2$ and itself, so it goes in this fashion..

So, the number of permutations of $[12]$ of order $12$ is $11\cdot 10 \cdots 2\cdot 1=11!$

Are my solutions valid for $a,b$ and $c$?

Answer 1

Unfortunately, it's more subtle than that -- I initially thought the count for elements of order $12$ was correct, but as another answer reminded me, even this isn't achieved only by $12$-cycles, as a permutation like $(1234)(567)$ will also have order $12$, the LCM of its cycle lengths.

As a comment has recently (as of when I started writing!) pointed out, the issue is that products of disjoint $3$-cycles also have order $3$, but aren't counted by your argument (it's similar with elements of order $4$, but even worse -- you can have $2$- and $4$-cycles there, instead of all cycles having the same length, as long as you use at least one $4$-cycle. As I think about it, it's actually horrific...).

I think cycle notation is really the right tool for the job, but even then, it's kind of a pain. I kept getting it wrong, and asked Sage for help counting elements of order $3$ in $S_9$ (it runs out of memory in $S_{12}$, heh).

So, as an example, let's count $3$-cycles in $S_9$. They can take one of three shapes:

$$(\ \underline{\ \ }\ \underline{\ \ }\ \underline{\ \ }\ ),$$ $$ (\ \underline{\ \ }\ \underline{\ \ }\ \underline{\ \ }\ ) (\ \underline{\ \ }\ \underline{\ \ }\ \underline{\ \ }\ ), $$ or $$ (\ \underline{\ \ }\ \underline{\ \ }\ \underline{\ \ }\ ) (\ \underline{\ \ }\ \underline{\ \ }\ \underline{\ \ }\ ) (\ \underline{\ \ }\ \underline{\ \ }\ \underline{\ \ }\ ). $$

Counting the first kind isn't so bad; we choose $3$ elements to fill the three spots, and remember that each $3$-element subset gives $2$ distinct $3$-cycles; there are $2 \cdot {9 \choose 3}$ such elements.

In the second case, we count ways to build the individual $3$-cycles,

$$\underbrace{(\ \underline{\ \ }\ \underline{\ \ }\ \underline{\ \ }\ )}_{2 \cdot {9 \choose 3}} \underbrace{(\ \underline{\ \ }\ \underline{\ \ }\ \underline{\ \ }\ )}_{2 \cdot {6 \choose 3}},$$ but realize that we've chosen these two cycles to appear in that order, so we've over-counted by a factor of $2!$. Hence, there are $\frac{2 \cdot 2}{2!} {9 \choose 3} \cdot {6 \choose 3}$ elements of this shape.

Finally, the one that I kept underestimating, we have the $3$-disjoint-$3$-cycles case. It's similar, but for some reason gave me trouble. As above, we count ways to build the $3$-cycles, then correct, having over-counted:

$$\underbrace{(\ \underline{\ \ }\ \underline{\ \ }\ \underline{\ \ }\ )}_{2 \cdot {9 \choose 3}} \underbrace{(\ \underline{\ \ }\ \underline{\ \ }\ \underline{\ \ }\ )}_{2 \cdot {6 \choose 3}} \underbrace{(\ \underline{\ \ }\ \underline{\ \ }\ \underline{\ \ }\ )}_{2 \cdot {3 \choose 3} = 2},$$ for a total of $\frac{2 \cdot 2 \cdot 2}{3!} {9\choose 3} \cdot {6 \choose 3}$.

Adding the permutations from the three cases, we do get $5768$, agreeing with the Sage computation.

---

Counting elements of order $4$ in $S_{12}$, it looks like you can have the following $9$ shapes: $4,\ 4 + 2,\ 4 + 2 + 2,\ 4 + 2 + 2 + 2,\ 4 + 2 + 2 + 2 + 2$ (where $4 + 2 + 2 + 2$ refers to a permutation like $(1234)(56)(78)(9\ 10)$)

$4 + 4,\ 4 + 4 + 2,\ 4 + 4 + 2 + 2$ and

$4 + 4 + 4$

Answer 2

The key observation here is that a permutation of $[n]$ of order $k$ has the property that the least common multiple of all it's cycle lengths is $k$. For this question we have $n=12$.

So, for $k=3$ we can only have cycle lengths of $1$ and $3$ but we must have at least $1$ cycle of length $3$. The exponential generating function for cycles of length $1$ is $e^x$ and for at least $1$ cycle of length $3$ is $e^{x^3/3}-1$ so the answer to (a) is:

$$[x^{12}/12!]e^x(e^{x^3/3}-1)=776\,600\tag{Answer (a)}$$

Just out of interest the expansion of the first $12$ terms of this function is:

$$\begin{multline}\frac{353}{217728} \, x^{12} + \frac{1291}{362880} \, x^{11} + \\ \frac{97}{11340} \, x^{10} + \frac{103}{6480} \, x^{9} + \frac{11}{360} \, x^{8} + \frac{5}{72} \, x^{7} + \frac{1}{9} \, x^{6} + \frac{1}{6} \, x^{5} + \\ \frac{1}{3} \, x^{4} + \frac{1}{3} \, x^{3}\end{multline}$$

as given by sage.

For $k=4$ we can have cycles of lengths $1,2$ and $4$ and must have at least $1$ cycle of length $4$. The respective generating functions for these are $e^x$, $e^{x^2/2}$ and $e^{x^4/4}-1$ therefore the answer to (b) is

$$[x^{12}/12!]e^xe^{x^2/2}(e^{x^4/4}-1)=9\,753\,480\tag{Answer (b)}$$

Again, out of interest, the expansion of the first $12$ terms of this function is

$$\begin{multline}\frac{821}{40320} \, x^{12} + \\ \frac{163}{5040} \, x^{11} + \frac{83}{1440} \, x^{10} + \frac{41}{480} \, x^{9} + \frac{13}{96} \, x^{8} + \frac{1}{6} \, x^{7} + \frac{1}{4} \, x^{6} + \frac{1}{4} \, x^{5} + \\ \frac{1}{4} \, x^{4}\end{multline}$$

For $k=12=2^2\cdot 3$ we can have cycles of lengths $1,2,3,4,6$ and $12$ and we must have either at least $1$ each of a $3$-cycle and $4$-cycle or at least $1$ $12$-cycle. The respective generating functions are

$$f_{3\cap 4}(x)=e^xe^{x^2/2}(e^{x^3/3}-1)(e^{x^4/4}-1)e^{x^6/6}e^{x^{12}/12}$$ $$f_{12}(x)=e^xe^{x^2/2}e^{x^3/3}e^{x^4/4}e^{x^6/6}(e^{x^{12}/12}-1)\, .$$

By inclusion-exclusion the exponential generating function for cycles of order $12$ is

$$F(x)=f_{3\cap 4}(x)+f_{12}(x)-f_{3\cap 4\cap 12}(x)$$

Finally, for (c) we want

$$[x^{12}/12!]F(x)=60\,207\,840\tag{Answer (c)}$$

The expansion of the first $12$ terms of $F(x)$ is

$$\frac{181}{1440} \, x^{12} + \frac{17}{288} \, x^{11} + \frac{5}{72} \, x^{10} + \frac{1}{12} \, x^{9} + \frac{1}{12} \, x^{8} + \frac{1}{12} \, x^{7}$$

---

Edit: Reference

For more on cycle egfs see p.81 of generatingfunctionology pdf.