# 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

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}$$
• $\mathcal{O}(2^n) \in \mathcal{O}(n!)$ but $\mathcal{O}(n!) \notin \mathcal{O}(2^n)$ – kelalaka Sep 11 '18 at 5:15