# Keys-space for a restricted substitution cipher

How can one calculate the key-space for a restricted substitution cipher? A restricted substitution cipher is one where no letter is assigned to itself. For an alphabet with 26 letters how many keys are there for a restricted substitution cipher? What is the correct way to approach this question? I have been adviced to look into cycle notations, Markov chains and the structure of the symmetric group and its conjugacy classes.

• isn't it 25!. Simply you have 25 for the first position, then 24 for the second, and so on. – kelalaka Sep 9 '18 at 20:23
• @kelalaka Alright, let's say that 'a' can be assigned in 25 ways because we can't fix 'a' with 'A', and 'b' can be assigned in 24 ways because 'a' is already assigned with one and 'b' can't be assigned with 'B'. But, what if 'a' was assigned with 'B', this would make the number of options to be 25. – Rai Sep 9 '18 at 23:01

## 1 Answer

It is called derangement, see Wikipedia. Also, in Mathematics Stack Exchange 1, 2

Number of derangements of n elements $$=\sum\limits_{k = 0}^{n}(-1)^k\frac{n!}{k!}$$

When n = 26 the result is 148362637348470135821287825 $$\approx 2^{87}$$

• That seems a bit too much. The derangement can be approximated as !n = (n!/e), and for n = 26, that's of the order of 26, not 87 as you said. – Rai Sep 10 '18 at 23:44
• $\mathcal{O}(2^n) \in \mathcal{O}(n!)$ but $\mathcal{O}(n!) \notin \mathcal{O}(2^n)$ – kelalaka Sep 11 '18 at 5:15