Finding number of permutations of order $k$ in $S_n$

Question

I want to find the number of permutations of order $k$ in $S_n$.

I found this very helpful answer that elaborates specifically how to do it. But I'm having trouble with the step 1 of that answer.

As far as I understand, order of a permutation is the least common multiple of lengths of disjoint cycles. So, in symbols, I'd want to write a permutation $\sigma$ as product of disjoint cycles of lengths $r_1, r_2, \ldots, r_m$ such that $\text{lcm}(r_1, r_2, \ldots, r_m)=k$ and $\sum r_i=n$, so from this I conclude that each cycle length $r_i$ must be a divisor of $k$. Okay so far so good.

So now, I'd want to write down $n$ as a sum of divisors of $k$ such that the $\textrm{lcm}$ of the divisors is $k$. Now if $n$ is small, I don't think I have a problem because there are only so many divisors or cycle structures possible. But I keep messing up when $n$ is big. I keep missing some partitions of $n$ when I write them down manually and it takes a lot of time.

Question: What would be a systematic way to methodically do step 1 without missing any partitions whose $\text{lcm}$ is $k$ in my exams where I have very limited time to solve a question like this? What should be my line of thought while approaching such a question?

Answer 1

Take prime factorization of $k=p_1^{e_1}\cdots p_m^{e_m},$ $m$ is the number of $k$'s prime factors, $e_j\in \mathbb{Z}_+.$ Then your question becomes:

Let $r_i=p_1^{e_{i,1}}\cdots p_m^{e_{i,m}}\ge 1.$ You will have at most $n$ cycles to let $\sum_{i} r_i=n,$ so $1\le i\le n.$ To let $\operatorname{lcm}(r_i)=k,$ you need to ensure

1. $0\le e_{i,j}\le e_j;$
2. $\max_i e_{i,j}=e_j.$

So you're working with an non-negative integer matrix $(e_{i,j})_{n\times m},$ each column has restriction like above, and you don't care about the permutation of rows. So you can have an order of rows: For $b>a,$ $e_{b,1}\le e_{a,1}$, or $e_{b,1}=e_{a,1}$ but $e_{b,2}\le e_{a,2}$, or ...

Now you have all matrixes with $\operatorname{lcm}(r_i)=k,$ but not for $\sum_i r_i=n$ yet. But this is easy. Take out all zero rows, i.e. eliminate $r_i=1$. If the remaining $\{r_i\}$ satisfies $\sum_i r_i\le n,$ then the matrix counts. As you can add $r_i=1$ to complement the rest part.

So the complete method is:

1. Start with row $1$, and start with the largest order of rows you defined, i.e. let $r_1=k$ first.
2. Go down to fill the matrix with elements as large as possible, unless the pattern has already used. If no element can be filled, clear current rows, go up to change the previous row.
3. Fill until $\sum_i r_i\ge n.$ Clear current rows, go to step $2$.

Remember in all step, you need to ensure the matrix fulfill the condition above to have $\operatorname{lcm}(r_i)=k$. When you use step $2$ recurrently to get $r_1=p_1^{e_1},$ ..., $r_m=p_m^{e_m}$, you finish your method because it's the smallest element that fulfill the condition.

Remark: the order of rows is like lexicographical order, like $$(3,3,3)>(3,3,2)>...>(2,3,3)>(2,3,2)...>(0,0,1)>(0,0,0)$$ This gives you the way to count without missing.

So actually you have two lexicographical order: one for rows to avoid repeat count; the other for matrices (i.e. patterns of $\{r_i\}$) to count them without missing.

---

For an example: $p=12=2^2\cdot 3,$ $m=2.$ Let $n=15.$ Then $$ \begin{bmatrix} 2&1\\ 1&0 \end{bmatrix}, \begin{bmatrix} 2&1\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&1\\ \end{bmatrix}, \begin{bmatrix} 2&0\\ 2&0\\ 2&0\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 2&0\\ 1&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 2&0\\ 1&0\\ 1&0\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 2&0\\ 1&0\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 2&0\\ 0&1\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 2&0\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 1&1\\ 1&0\\ 1&0\\ \end{bmatrix}, \begin{bmatrix} 2&0\\ 1&1\\ 1&0\\ 0&1\\ \end{bmatrix}, \begin{bmatrix} 2&0\\ 1&1\\ 0&1\\ \end{bmatrix}, \begin{bmatrix} 2&0\\ 1&0\\ 1&0\\ 1&0\\ 1&0\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 1&0\\ 1&0\\ 1&0\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 1&0\\ 1&0\\ 0&1\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 1&0\\ 1&0\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 1&0\\ 0&1\\ 0&1\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 1&0\\ 0&1\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 1&0\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 0&1\\ 0&1\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 0&1\\ 0&1 \end{bmatrix}, \begin{bmatrix} 2&0\\ 0&1 \end{bmatrix}. $$

22 patterns in total.

For an easier one to varify, let $p=2\cdot 3,$ $n=8:$ $$ \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}, \begin{bmatrix} 1&1 \end{bmatrix}, \begin{bmatrix} 1&0\\ 1&0\\ 0&1 \end{bmatrix}, \begin{bmatrix} 1&0\\ 0&1\\ 0&1 \end{bmatrix}, \begin{bmatrix} 1&0\\ 0&1 \end{bmatrix}. $$

5 patterns in total.

Maybe use computer to assist is a better way, once you admit this method.