Number of Involuntory Keys in Permutation Cipher

I've came with the following problem from the Theory and Practice book by Stinson-Paterson. It states the following:

2.17

(a) Prove that a permutation $\pi$ in the Permutation Cipher is an involuntory kei iff (if and only if) $\pi(i) = j$ implies $\pi(j) = > i$, for all $i,j \in \{1,...,m \}$.

(b) Determine the number of involutory keys in the Permutation Cipher for $m = 2,3,4,5, $ and 6.

I've proved the first item, showing that the indices of the $x's$ and $y's$ remain the same, however I don't have any hint to determine the second item b, this is, I'm not sure of the role of the key in this type of cipher; any clarifications, indeed one clear answer would be good.

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]