[Math] Determine the number of involutory keys in the Permutation Cipher for m = 5 and 6.

combinatoricscryptography

I know that the number of involuntary keys in m = 4 is 10 from this article: Involutory Key of Permutation Cipher

Although, I'm not seeing how this person concluded that (4, 2) = 6 and this problem makes it very difficult to expand that problem onto m = 5 and 6.

Best Answer

How many involutions do we have for $n=5$? The cycle structure (we only have cycles of length 2 or 1 as in he tlinked answer) can only be $2,1,1,1$ or $2,2,1$. The former has $\binom{5}{2}=10$ realisations (just pick an unordered pair from $\{1,2,3,4,5\}$). The other has $5$ ways to pick the fixed point and then pick the unique point among $3$ remaining that will be in a cycle with the minimum of the remaining points. (say: we pick $2$ as fixed then $1$ is the minimal remaining point, and we pick one element from $\{3,4,5\}$ say $5$ to be in a cycle with it. The last 2 are the final cycle, so we get $(1)(25)(34)$ as a realisation, etc.)

So in all we have $10 + 5 \times 3 = 25$ involutions, plus $1$ if we count the identity too, (a bit of a silly "cipher"). I'm only counting exact order $2$ with $25$.

For $n=6$ we can have $2,2,2$ as well, etc. etc. Try it.

For the complete sequence see the online encyclopedia of integer sequences

The easiest way to compute it in practice, I think, is using the recursion $$i_n = i_{n-1} + (n-1)i_{n-2}, i_1 = 1, i_2 = 2$$ where $i_n$ is the number of involutions on $\{1,\ldots,n\}$: the first term is for the involutions that fix $n$, for the other term we pick one $j < n$ such that $(j n)$ form a cycle and consider involutions on the remaining $n-2$ points.

Related Question