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

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?

• Let $P_{k}^{n}$ be the number of permutations of order $k$ in $S_{n}$. An easier question is to find the number of permutations of order divisible by $k$. This is because you just have to partition $n$ into arbitrary divisors of $k$, and not have to worry about the final lcm. Denote this number to be $D^{n}_{k}$. We can find $P_{k}^{n}$ from $D^{n}_{k}$ using the inclusion-exclusion principle. Eg: assume $k$ has exactly $2$ distinct prime factors, $e_{1}$, $e_{2}$ Ie. $k = e_{1}^{r_1} e_{2}^{r_2}$. Then we have $P_{k}^{n} = D_{k}^{n} - D_{k/e_1}^{n} - D_{k/e_2}^{n} + D_{k/(e_1 e_2)}^{n}$ Nov 25, 2021 at 7:32
• I meant "dividing $k$" instead of "divisible by $k$". The same alternating sign pattern generalizes for any number of prime factors. Nov 25, 2021 at 9:03

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.

• I don't know whether there is an elegant formula to do it. Nov 16, 2021 at 12:41
• I'm confused by your subscripts, for example what is your $m$ here? Is it the number of cycles? Then what does $\sum\limits_{i=1}^{n} r_i = n$ mean?... Did you mean $\sum\limits_{i=1}^{m} r_i = n$ instead? What is $m$? Nov 16, 2021 at 22:39
• @William $m$ is the number of $k$'s prime factors. As $r_i\ge 1,$ the upper bound of the number of cycles shall be $n$. You need this bound to ensure you can count them one by one. However in many (all) times you don't need so much cycles. You can let redundant $r_i=0$ to show you don't need these cycles. Nov 17, 2021 at 3:25
• I'll be honest, at my level I find this a little too complicated. Also I don't think I'd have enough time to carry this out in an exam. I've updated my question to include that I need a general line of thought while solving such questions in a limited time. Nov 18, 2021 at 11:58