How many elements of order $k$ are in $S_n$?

I need to find how many elements of order $k$ are in $S_n$ (where $k \leq n$).

So if $k$ is prime, it's easy: $k$ can't be the $\mathrm{lcm}$ of any integers besides itself and one's (which we're omitting).
So the length of the cycle then must be $k$, and the number of elements with $k$-length cycle representation in $S_n$ is given by $$\dbinom{n}{k}(k-1)!$$ But it gets really tricky when $k$ is not a prime number...
I need to consider every set of integers that can divide $k$, and then, for every set, I need to find how many elements of that form are there...
Or maybe I'm missing something here?

I need help figuring that out. thanks in advanced!

• I think it is unlikely that there is any straightforward formula for this in terms of $k$ and $n$. It would not be too hard to compute it for any given $k$ and $n$. Why do you need to find this out? Jan 4, 2014 at 17:15
• Hi Derek. This question appears in an exercise we got from our professor. Jan 4, 2014 at 17:18
• Notice that every $a\in S_n$ can be expressed as composition of cycles. If $a=c_1...c_l$ then $o(a)=lcm(o(c_1),...,o(c_l))$. Its easy to count number of such permutations for decomposition of given form. Now u can just sum over all possible forms of decomposition. Its not the prettiest formula but its something. Jan 4, 2014 at 17:26
• Your count for $k$ prime is wrong as soon as $n\ge 2k$ Jan 4, 2014 at 17:29
• @HagenvonEitzen Yeah, you're right, I miscalculated. That makes this question even worse... :-) Thanks user52045, I'll give it a try. Jan 4, 2014 at 17:38

Consider all cycle types of permutations in $S_{n}$ which have order $k$. Recalling that $\sigma, \tau \in S_{n}$ are conjugate if and only if they have the same cycle type, then it should just then be a matter of finding the number of conjugates of each cycle type with order $k$. This is given by

$$\frac{n!}{\prod_{i=1}^{s}(k_{i}! m_{i}^{k_{i}})}$$

where for each $i \in \{0, 1, \dots, s\}$, $m_i$ is a distinct integer appearing in the cycle type of your permutation, and $k_i$ gives the number of cycles of length $m_{i}$.

This one can be done by inclusion-exclusion. Note that the combinatorial class $\mathcal{Q}$ of permutations whose order divides $k$ is given by $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{Q} = \textsc{SET}\left(\sum_{d|k} \textsc{CYC}_{=d}(\mathcal{Z})\right).$$ Translation to exponential generating functions we obtain the EGF of permutations whose order divides $k$, which is $$Q_k(z) = \exp\left(\sum_{d|k} \frac{z^d}{d}\right).$$ Now we can use this generating function to count permutations of order exactly $k$ by inclusion-exclusion. Consider the Hasse diagram of the divisor poset of $k.$ By inclusion-exclusion we label the top node, which is $k$, with a weight of one representing permutations of order exactly $k$ and descend along the chains, labelling every node $d$ with the appropriate weight to make the weights of the poset spanned by $d$ and $k$ sum to zero.

Let $f_1(d)$ be the weight function. The above process gives the following two equations: $$f_1(k) = 1 \quad\text{and for}\quad d|k,\; d<k,\quad \sum_{m|k/d} f_1(dm) = 0.$$ Now introduce $f_2(d) = f_1(k/d).$ The defining equations then become $$f_2(1) = 1 \quad\text{and for}\quad d|k,\; d>1,\quad \sum_{m|d} f_2(m) = 0.$$ But this is the defining equation of the Mobius function $\mu(d)$ from basic number theory. Therefore the weight of the inclusion-exclusion terms is given by $\mu(k/d)$ and we finally have the EGF $$Q(z) = \sum_{d|k} \mu(k/d) \times Q_d(z) = \sum_{d|k} \mu(k/d) \exp\left(\sum_{m|d} \frac{z^m}{m}\right).$$ The desired count is then given by $$n! [z^n] Q(z).$$

This formula produces e.g. for $k=6$ the EGF $$Q(z) = {{\rm e}^{z}}-{{\rm e}^{z+1/2\,{z}^{2}}}-{{\rm e}^{z+1/3\,{z}^{3}}}+{{\rm e}^{z+1/2\,{ z}^{2}+1/3\,{z}^{3}+1/6\,{z}^{6}}}$$ with the sequence of values starting at $n=5$ $$20, 240, 1470, 10640, 83160, 584640, 4496030, 42658440, 371762820, 3594871280,\ldots$$ which is OEIS A061121.

For $k=8$ we get the EGF $$Q(z) = -{{\rm e}^{z+1/2\,{z}^{2}+1/4\,{z}^{4}}}+{{\rm e}^{z+1/2\,{z}^{2}+1/4\,{z}^{4}+1/8\,{z }^{8}}}$$ with the sequence of values starting at $n=8$ $$5040, 45360, 453600, 3326400, 39916800, 363242880, 3874590720, 34767532800,\ldots$$ which is OEIS A061122.

Finally for $k=12$ we get the EGF $$Q(z) = {{\rm e}^{z+1/2\,{z}^{2}}}-{{\rm e}^{z+1/2\,{z}^{2}+1/4\,{z}^{4}}}-{{\rm e}^{z+1/2\,{z }^{2}+1/3\,{z}^{3}+1/6\,{z}^{6}}}+{{\rm e}^{z+1/2\,{z}^{2}+1/3\,{z}^{3}+1/4\,{z}^{4}+1 /6\,{z}^{6}+1/12\,{z}^{12}}}$$ with the sequence of values starting at $n=7$ $$420, 3360, 30240, 403200, 4019400, 80166240, 965284320, 12173441280, 162850287600,\ldots$$ which is OEIS A061125.

Remark as of Mon Jul 28 2014. The argument above is correct but it can be simplified by recognizing the Moebius inversion formula that appears.

Addendum as of Sat Apr 22 2017. As rightly pointed out by @Nesa the EGF yields the correct data but is impracticable for $n$ large. We may instead use the recursive formula by Lovasz for the cycle index of the symmetric group, which is

$$Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l Z(S_{n-l}) \quad\text{where}\quad Z(S_0) = 1.$$

Restricting to cycles of length a divisor of $k$ we obtain

$$Z_k(S_n) = \frac{1}{n} \sum_{l|k \wedge 1\le l\le n} a_l Z_k(S_{n-l}) \quad\text{where}\quad Z_k(S_0) = 1.$$

We then retain only those conjugacy classes (which are represented by partitions) with LCM of the cycle lengths equal to $k$. Further optimization is possible here (we tried to keep it simple) which the reader is invited to investigate. Some examples for the optimized routine compared to Taylor series applied to the EGF and implemented in Maple are

• permutations on $50$ elements of order exactly $24$ in $0.8s$ (as opposed to $31s$, $831$ Mb memory allocated):

$$62691738121269819754220487957220800432035041174469549752320000$$

• permutations on $50$ elements of order exactly $30$ in $0.6s$ (as opposed to $35s$, $846$ Mb memory allocated):

$$105557285434280619538495502609995618378421158878971545429804800$$

• permutations on $50$ elements of order exactly $35$ in $0.01s$ (as opposed to $13s$, $595$ Mb memory allocated):

$$14311697149323256258802803652030609474009628711255472000512000.$$

The Maple code that was used to compare the EGF to the cycle index goes as follows.

with(numtheory):

pet_cycleind_symm_divk :=
proc(n, k)
option remember;
local lseq;

if n=0 then return 1; fi;

lseq := select(l -> l <= n, divisors(k));

expand(1/n*
pet_cycleind_symm_divk(n-l, k), l in lseq));
end;

QAUX := m -> exp(add(z^d/d, d in divisors(m)));

Q := k -> add(mobius(k/d)*QAUX(d), d in divisors(k));

A := (n, k) -> n!*coeftayl(Q(k), z=0, n);

AOPT :=
proc(n, k)
option remember;
local idx, term, res, ord;

if n = 1 then
idx := [a[1]]
else
idx := pet_cycleind_symm_divk(n, k);
fi;

res := 0;
for term in idx do
ord :=
lcm(seq(op(1, var), var in indets(term)));

if ord = k then
res := res + lcoeff(term);
fi;
od;

n!*res;
end;

• @Marko_Riedel using the exponential generating function seems very expensive computationally, I think for up to some $N$ with $k$ made up of small prime factors even using the recursive formula for the cycle index and taking the $index(k)$ element is faster
– Nesa
Apr 20, 2017 at 23:12
• Thank you for the pointer, the implementation including examples is found above. Apr 22, 2017 at 0:52
• @Marko_Riedel Can you give a hint on what further optimisation you are meaning? The only thing I could think of is partitioning the monomials by LCM already in the $Z_{k}(S_{i})$ (not only at the end in $Z_{k}(S_{n})$) after having calculated it. (So e.g. if we have $4a_{1}a_{2}a_{12}+7a_{1}^8a_{3}a_{4}$ we reduce it to $11a_{12}$)
– Nesa
May 5, 2017 at 14:29