Elements that are their own inverses in a symmetric group.

Question

How many elements are their own inverses in $S_6$? I'm having a hard time figuring out how to calculate such a thing.

Answer 1

Here are the key facts:

• A permutation is its own inverse iff it has order $2$. (Such permutations are called involutions.)

• The order of a permutation is the lcm of the orders of the cycles in its cycle decomposition.

This should give you the type of all possible cycle decompositions.

Answer 2

In S6, here are three types of permutations of order 2: a the transpostions (ij) that swap the digits i and j (for i and j different digits between 1 and 6), the double transpostions (ij)(kl), where i, j, k, l are four different digits between 1 and 6, and the triple transposition (ij)(kl)(mn), where i,j,k,l,m,n are six different digits between 1 and 6.

Obviously the number of transpositions (ij) is 6 . 5 / 2, which is 15.

For the double transpositions, the transformation of order 2 will be $(1/2((6.5)/2)((4.3)/2))$ =45.

For the triple transposition, it will be $(1/3((6.5)/2)((4.3)/2)((2.1)/2))=30$

And also since identity is self inverse element too Therefore total number of elements of order 2 in S6 = 15+45+30+1 =91.

Answer 3

Direct counting gives us a simple formula: As pointed out by lhf, elements that are their own inverses in $S_n$ are called involutions and have order $2$ and hence must each consist of a product of disjoint transpositions and fixed points.

For a fixed $k$, $0 \leq k \leq \bigg\lfloor \dfrac{n}{2}\bigg \rfloor$, we may write our involution as a product of $k$ disjoint transpositions and $n-k$ fixed points as follows: first choose $2k$ elements out of $n$ in $\displaystyle \binom{n}{2k}$ ways and distribute them into the $k$ unordered $2-$cycles in $\displaystyle \dfrac{\binom{2k}{k}}{k!\times 2^k}$ ways.

Simplifying and summing over $k$, we get $I_n =\displaystyle \sum_{k=0}^{\lfloor \frac{n}{2}\rfloor}\binom{n}{2k}(2k-1)!!$ where $(2k-1)!! = 1\times 3 \ldots \times 2k-1$.

This tells us that $I_6 = 76$. This Wolfram page has more details on permutation involutions.

Answer 4

One approach is to say that every element is permuted with one other element or with itself.

Let's suppose you want such a permutation of $S_n$ with $k$ elements paired with themselves. There are two ways to construct this:

• Take such a permutation of $S_{n-1}$ with $k-1$ elements paired with themselves, and add on an extra element pared with itself.

• Take such a permutation of $S_{n-1}$ with $k+1$ elements paired with themselves, and add on an extra element pared with one of the earlier self-paired elements ($k+1$ choices).

So if $T(n,k)$ is the number of such elements then we can say

$$T(n,k)=T(n-1,k-1)+(k+1)T(n-1,k+1)$$ starting with $T(0,0)=1$ and $T(0,k)=0$ for $k \not=0$, and it is an easy calculation to get the small values for $T$:

n \ k     0     1     2     3     4     5     6 
                       
0         1        
1         0     1
2         1     0     1
3         0     3     0     1
4         3     0     6     0     1
5         0    15     0    10     0     1 
6        15     0    45     0    15     0     1 

You can take the row sums of these to count the self inverse permutations of $S_n$: $1,1,2,4,10,26,76,\ldots$ where the answer to your question on $S_6$ is $76$.

You can also work out a few more terms and look for this on OEIS to find it is sequence A000085, which gives a lot more information, including me saying two decades ago

Sequence starts 1, 1, 2, 4, 10, ... because possibilities are {}, {A}, {AB, BA}, {ABC, ACB, BAC, CBA}, {ABCD, ABDC, ACBD, ADCB, BACD, BADC, CBAD, CDAB, DBCA, DCBA}.