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

Advertisements

1 Comment

Filed under Combinatorics, Number theory

One response to “Number of permutations of prime order

  1. Pingback: Binomial sum modulo prime power | Samin Riasat's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s