I'm looking to find all the Involutory keys for the permutation cipher where m=4. A key where ek(x) = dk(x)
I notice that a Non-Involuntary Key for a permutation cipher in m=4 is a key where we have a 3 cycle. So for example the key (1,3,4,2)
While a Involutory key for a permutation cipher in m=4 is one that is composed of 2 cycles. For example (1,2,4,3)
So Basically where an element is swapped with only one other element. I have the following cases
(x1 -> x1) (x2 -> x2) (x3 -> x4)
i.e. Two numbers are fixed to themselves and one isn't
or
(x1->x2)(x2->x3)
i.e. Two numbers are swapped with one another
or
(x1 -> x1)(x2 -> x2)(x3 -> x3)(x4 -> x4)
i.e Each number is fixed to itself.
From these cases I'm confused how I would deduce the number of involutory keys. For example in the case if I have 4 choices for the first fixed number multiplied by 3 choices for the second fixed number and 1 choice for the last two fixed numbers I'd have 12 choices.
But combining that with the second case I'd already be at 24 different permutations which cant possibly be right.
A key for a permutation cipher is of course a permutation $\sigma \in S_n$.
It is self-inverse iff $\sigma^2 = e$, where $e$ is the identity permutation.
We can write any $\sigma \in S_n$ as a product of disjoint cycles in an essentially unique way (up to order of the cycles and leaving out or adding 1-cycles like $(x)$), and so we need all cycles of $\sigma$ to be self-inverse as well. So we can only use $2$-cycles and $1$-cycles. Of course $e$ itself (all $1$-cycles) is one solution. Then we have the cycle structure $2,1,1 $ of which we have $\binom{4}{2} = 6$ (we pick the two points in the $2$-cycle in an unordered way from the $4$ points. And finally we have cycle structure $2,2$, of which there are $\frac{4!}{2! 2! 2!} = \frac{24}{8} = 3$ (or by hand $(13)(24), (12)(34),(14)(23)$).
So we have $1 + 6 + 3 = 10$ many self-inverse keys.