Elements that are their own inverses in a symmetric group. How many elements are their own inverses in $S_6$? I'm having a hard time figuring out how to calculate such a thing.
 A: 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.
A: 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.
A: 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}.

A: 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.
