Number of permutations of order 2

Let \sigma\in S_n be an element of order 2. Then \sigma must be a product of k\ge 1 disjoint transpositions. Hence \sigma can be chosen in

\displaystyle\frac{1}{k!}\binom n2\binom{n-2}{2}\cdots\binom{n-2k+2}{2}=\frac{n!}{k!(n-2k)!2^k}

ways. So there are exactly

\displaystyle\boxed{\sum_{k=1}^{\lfloor n/2\rfloor}\frac{n!}{k!(n-2k)!2^k}}

elements of order 2 in S_n.

This can also be expressed in terms of the double factorial

\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}(2k-1)!!

The following table lists several values of n (left column) along with the number of elements of order 2 in S_n:

Screenshot 2015-03-15 20.54.56

An interesting feature of the table is that the entries on the second column, except for the first row, are all odd. This is true in general and is not difficult to prove. Using the double factorial notation, the number of elements of order 2 is

\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}(2k-1)!!\equiv \sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}\pmod 2

Using the binomial theorem for (1+1)^n and (1-1)^n one deduces

\displaystyle\sum_{k=1}^{\lfloor n/2\rfloor}\binom{n}{2k}=2^{n-1}-1\equiv 1\pmod 2

as expected. Thus

Fact. The number of elements of order 2 in S_n is odd for every n>1.

Advertisements

1 Comment

Filed under Combinatorics

One response to “Number of permutations of order 2

  1. Pingback: Number of permutations of prime order | 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