5
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ In $a)$, the issue is that yes, a permutation of three numbers amongst themselves gives an order three permutation, but the converse is not true. That is, every permutation of order three is not of this form. For example, the permutation $(123)(456)$ (in cycle notation) also has order $3$, although six elements are being permuted. Also in general a formula for the numbers of order $k$ in $[n]$ is not known. $\endgroup$ – астон вілла олоф мэллбэрг Mar 30 '18 at 1:19
  • $\begingroup$ So, I missed those possibilities @астонвіллаолофмэллбэрг $\endgroup$ – Leyla Alkan Mar 30 '18 at 1:24
  • $\begingroup$ Yes, that is the case. I wish that you can do this problem in some simple manner but it looks like you will have to be very careful and have lots of cases. $\endgroup$ – астон вілла олоф мэллбэрг Mar 30 '18 at 1:26
  • $\begingroup$ To be honest, at first it seemed to me impossible to compute the right number of all the permutations correctly, then I just gave it a try to see what happens $\endgroup$ – Leyla Alkan Mar 30 '18 at 1:29
  • $\begingroup$ Yes. Maybe you should try it for smaller $[n]$ first and see a pattern. $\endgroup$ – астон вілла олоф мэллбэрг Mar 30 '18 at 1:31
3
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Excellent! It took me several minutes to understand fully but finally I'm content with your answer. Thanks, it helped a lot! $\endgroup$ – Leyla Alkan Mar 30 '18 at 2:28
  • $\begingroup$ I'm glad to hear it, and you're quite welcome! $\endgroup$ – pjs36 Mar 30 '18 at 2:38
  • $\begingroup$ Be careful here that you are not counting the question case=12, one of either the questioner or answerer should fit his data to the other in order to remove confusion for a naive beholder thanks. $\endgroup$ – Abr001am Mar 30 '18 at 13:35
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It seems that we underestimated the c-part and only considered cycle of order $12$ whereas there are also disjoint cycle products of kind: $4+3, 4+3+3, 4+3+3+2, 4+3+2+2, 4+4+3$ Btw, I do not have any information about exponential generating functions for cycles. (Interestingly, I didn't get notified for the last comment and for your answer.) $\endgroup$ – Leyla Alkan Mar 30 '18 at 21:46
  • $\begingroup$ You might not have been notified because I spotted a mistake and temporarily deleted whilst I edited. You are right that there are other disjoint cycle products. All that they need to satisfy is the lcm of their lengths is the order (in part (c) it is 12). Notice, that although I have allowed for length 6 it never contributed because we must have at least either 3+4 or 12, neither leave room for a 6. $\endgroup$ – N. Shales Mar 30 '18 at 22:16
  • 1
    $\begingroup$ I thought you might know about cycle egfs, you asked this question which suggested an acquaintance. In simple terms you have an egf for "cards" (these are the numbers to be permuted) to be placed in subsets (cycles) so that only non-cyclic order changes distinct (i.e. a cycle length $k$ has $k!/k$ distinct arrangements), here the order of the subsets (cycles) doesn't count. So $$A(x)=\sum_{k\ge 1}\frac{k!}{k}\frac{x^k}{k!}$$ $$B(x)=\sum_{l\ge 0}\frac{x^l}{l!}$$. Then do $B(A(x))$. $\endgroup$ – N. Shales Mar 30 '18 at 22:28
  • 1
    $\begingroup$ You should see that this gives a cycle egf of $$e^{x+x^2/2+x^3/3+\cdots}\, .$$ So $x^k$ enumerate permutations of cycle length $k$. So if we only want cycles of a particular length we only use those powers of $x$ e.g. $e^{x^2/2}$ for permutations with only 2-cycles. Additionally, if we must have at least 1 of a particular cycle length then we must subtract the case where that cycle isn't used e.g. If we must have at least 1 2-cycle the we use $e^{x^2/2}-1$. $\endgroup$ – N. Shales Mar 30 '18 at 22:44
  • 1
    $\begingroup$ Thanks for the explanations and alternative way you suggested! I'll first check the book, and then go all over your solution again. After that I can tell if I have further questions and let you know.. $\endgroup$ – Leyla Alkan Mar 30 '18 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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