# Number of permutations of prime order

In the last post we counted the number of elements of order 2 in the symmetric group $S_n$. In exactly the same way we can count the number of elements of order $p$, where $p$ is a prime number. Let this number be denoted by $N_p(n)$. Then

\displaystyle\begin{aligned}N_p(n)&=\sum_{k=1}^{\lfloor n/p\rfloor}\frac{(p-1)!^k}{k!}\binom np\binom{n-p}{p}\cdots\binom{n-pk+p}{p}\\ &=\sum_{k=1}^{\lfloor n/p\rfloor}\frac{n!}{k!(n-pk)!p^k}\\ &=\sum_{k=1}^{\lfloor n/p\rfloor}\binom{n}{pk}\frac{(pk)!}{k!p^k}.\end{aligned}

Here we adopt the convention $\binom nm=0$ if $m>n$. Note that

$\displaystyle\frac{(pk)!}{k!p^k}=\frac{(pk)!}{p\cdot 2p\cdots kp}\equiv (p-1)!^k\equiv (-1)^k\pmod p$

by Wilson’s theorem. So

$\displaystyle N_p(n)\equiv\sum_{k=1}^{\lfloor n/p\rfloor}(-1)^k\binom{n}{pk}\pmod p$.

If $n=n_rp^r+\cdots+n_1p+n_0$ and $k=k_{r}p^{r-1}+\cdots+k_2p+k_1$ are base $p$ expansions, then using Lucas’ theorem one has

$\displaystyle\binom{n}{pk}\equiv\binom{n_r}{k_r}\cdots\binom{n_1}{k_1}\pmod p$.

Therefore

\displaystyle\begin{aligned}N_p(n)&\equiv -1+\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^k\binom{n}{pk}\pmod p\\ &\equiv -1+\sum_{k=0}^{\lfloor n/p\rfloor}(-1)^{k_1+\cdots+k_r}\binom{n_r}{k_r}\cdots\binom{n_1}{k_1}\pmod p\\ &\equiv -1+\prod_{j=1}^r\sum_{k_j=0}^{n_j}(-1)^{k_j}\binom{n_j}{k_j}\pmod p\\ &\equiv -1\pmod p\end{aligned}

This generalizes the result from the previous post.

Corollary. The number of subgroups of order $p$ in $S_n$ is congruent to $1\pmod p$.

Proof. If there are $k$ subgroups of order $p$ in $S_n$, then $N_p(n)=k(p-1)\equiv -1\pmod p$ and so $k\equiv 1\pmod p$. $\square$