Involutions are in one-to-one correspondence with self-conjugate permutations (i.e., permutations that are their own inverse permutation)

The series is given in oeis A000085.

The formula for the number of involution permutations on $n$ letters is;

$$I(n) = 1 + \sum_{k=0}^{\lfloor (n-1)/2 \rfloor} \frac{1}{(k+1)!} \prod_{i=0}^k \binom{n-2i}{2}$$

**A little hand calculation**

First of all, identity permutation $\varepsilon$ is always an involution. Here we will use one line notation.

$m =2 $ then $\varepsilon = (1,2)$ and $(2,1)$ are the involutions.

$m =3 $ then $\varepsilon = (1,2,3)$, $(1,3,2)$,$(3,2,1)$, and $(2,1,3)$ are the 4 possible.

$m =4 $ then $\varepsilon = (1,2,3,4)$ and

- fix first $(1,a,b,c)$ then we have 3, by previous case; $(1,2,4,3),(1,4,3,2),(1,3,2,4)$
- fix second $(a,2,c,d)$ then we have 2, $(3,2,1,4),(4,2,3,1)$ ( one existed in the previous case)
- fix third $(a,b,3,d)$ then we have 1, $(2,1,3,4)$
- fix fourth $(a,b,c,4)$ then we have 0; all existed before.
- fixed double then $(4,2,3,1)$
- doubles $(3, 4, 1, 2),(2,1,4,3)$

**A Sagemath code for 5**

```
p = Permutation([1, 2,3,4,5])
for i in range(0,factorial(5)):
if p == p.inverse():
print(p)
p = p.next()
```

With output

```
[1, 2, 3, 4, 5]
[1, 2, 3, 5, 4]
[1, 2, 4, 3, 5]
[1, 2, 5, 4, 3]
[1, 3, 2, 4, 5]
[1, 3, 2, 5, 4]
[1, 4, 3, 2, 5]
[1, 4, 5, 2, 3]
[1, 5, 3, 4, 2]
[1, 5, 4, 3, 2]
[2, 1, 3, 4, 5]
[2, 1, 3, 5, 4]
[2, 1, 4, 3, 5]
[2, 1, 5, 4, 3]
[3, 2, 1, 4, 5]
[3, 2, 1, 5, 4]
[3, 4, 1, 2, 5]
[3, 5, 1, 4, 2]
[4, 2, 3, 1, 5]
[4, 2, 5, 1, 3]
[4, 3, 2, 1, 5]
[4, 5, 3, 1, 2]
[5, 2, 3, 4, 1]
[5, 2, 4, 3, 1]
[5, 3, 2, 4, 1]
[5, 4, 3, 2, 1]
```