Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Given a partial key for a mono-alphabetic substitution cipher (missing 11 letters), calculate the number $N$ of possible keys, given that no plaintext letter can be mapped to itself.

Ordinarily, the number of possible keys would be the number of derangements of the missing letters $!11$. However, 5 of the plaintext letters that are missing mappings already exist as mappings in the partial key, so logically it shouldn't matter what the mapping of those plaintext letters is, because they can never map to themselves.

So, I wonder if the number of possible keys is $N = 5! * !6$. That is:

(no. permutations of 5 already mapped free letters) * (no. derangements of the remaining 6)

The problem is that 5! * !6 = 31800 which is much less than !11 = 14684570 Intuitively, the set of derangements should be the smaller subset, so surely $N>!11$.

Am I getting something wrong in my arithmetic or am I completely missing the concepts?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

This is purely a counting problem. We want the number $N(n,m)$ of possible permutations of $n$ things, with the constraint that only $m$ among these things can map to themselves ($0\le m\le n$). The values in the question are $n=11$, $m=5$.

It holds that $N(n,n)=n!$ (that's the number of permutations of $n$ elements).

It holds that $N(n,0)=\text{}!n=\begin{cases} 1 &\text{if }n=0\\ \lfloor{{n!+1}\over e}\rfloor&\text{if }n>0\\ \end{cases}$
(that's the number of derangements of $n$ elements).

The computation made of $N(11,5)$ as $5!\cdot\text{}!(11-5)=31,800$ in the question is wrong, as noted: this is less than $!11=14,684,570$, when it should be above (but still less than $11!=39,916,800$). Two mistakes have been made:

  • the $m=5$ things that can be assigned without constraint among $n=11$ can be so in $n!\over(n-m)!$ ways, not $m!$ ways; fixing that, we would get ${11!\over(11-5)!}\cdot\text{}!(11-5)=14,691,600$, which is more credible;
  • but after first assigning $m=5$ unconstrained things, the assignments for the $n-m=6$ other things depend on how we arranged the unconstrained things (if we assigned one of the unconstrained things to an initially constrained thing, the later becomes unconstrained); therefore, the above $14,691,600$ is significantly too low.

Taking a deep breath, we can see that $N(n,m)$ can be obtained as $$\begin{cases} 1 &\text{if }n=0, m=0\\ 0 &\text{if }n=1, m=0\\ n\cdot N(n-1,n-1) &\text{if }n>0, m=n\\ (n-1)\cdot N(n-1,1) &\text{if }n>1, m=0\\ m\cdot N(n-1,m-1)+(n-m)\cdot N(n-1,m)&\text{if }0<m<n\\ \end{cases}$$ Justifications:

  • when $n=0, m=0$: there's a single method to map nothing; consistency with $0!=\text{}!0=1$.
  • when $n=1, m=0$: there's no permutation of one thing that does not map that thing to itself; consistency with $\text{}!1=0$.
  • when $n>0, m=n$: we assign an unconstrained thing to an unconstrained thing (thus in $n$ possible ways), leaving $n-1$ unconstrained things; that's the classic factorial recursion.
  • when $n>1, m=0$: we assign a constrained thing to a constrained thing other than itself (thus in $n-1$ possible ways), leaving $n-1$ things among which $1$ became unconstrained.
  • when $0<m<n$: we assign an unconstrained thing, either
    • to an unconstrained thing (thus in $m$ possible ways), leaving $n-1$ things among which $m-1$ unconstrained;
    • to a constrained thing (thus in $n-m$ possible ways), leaving $n-1$ things among which $m$ unconstrained including the one that became unconstrained.

I get $N(13,6)=3,597,143,040$, and $N(11,5)\equiv67\pmod{97}$.


If we don't mind that $m=n+1$ creeps in, $N(n,m)$ can also be obtained as $$\begin{cases} (n-1)\cdot N(n-1,1) &\text{if }n>0, m=0\\ m\cdot N(n-1,m-1)+(n-m)\cdot N(n-1,m)&\text{if }0<m\le n\\ 1 &\text{otherwise}\\ \end{cases}$$ or as $$\begin{cases} n\cdot N(n-1,n-1) &\text{if }n>0, m=n\\ m\cdot N(n-1,m)+(n-m-1)\cdot N(n-1,m+1)&\text{if }0\le m<n\\ 1 &\text{otherwise}\\ \end{cases}$$ Justification of the new relation when $0\le m<n$: we assign a constrained thing, either

  • to an unconstrained thing (thus in $m$ possible ways), leaving $n-1$ things among which $m$ unconstrained;
  • to a constrained thing other than itself (thus in $n-m-1$ possible ways), leaving $n-1$ things among which $m+1$ unconstrained including the one that became unconstrained.

Based on intuition confirmed by numerical evidence that $m\mapsto N(n,m)$ is close to exponential between $m=0$ and $m=n$, I assert that $$N(n,m)\approx n!\cdot e^{m/n-1}$$ This approximation is by excess when $m>0$. The error made is less than $4.0\%$ for $n\ge4$; less than $1.8\%$ for $n\ge8$; less than $1.0\%$ for $n\ge14$.

More rigourously stated: $$\forall r\in\mathbb R, 0\le r\le1\implies\lim_{n\rightarrow\infty}{n!\cdot e^{r-1}\over N(n,\lfloor r\cdot n\rfloor)}=1$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.