1
$\begingroup$

This is a question about basic combinatorics.

I recently watched again a youtube video about the Enigma cipher machine (in the Numberphile channel, https://www.youtube.com/watch?v=G2_Q9FoD-oQ), where the Enigma machine is briefly analyzed. In particular, they describe the number of different machine configurations, where the rotors and plugboard are set. The plugboard is basically an electric board where two letters are interchanged (e.g. letter 'q' is substituted by letter 'a' and 'a' by 'q'), having ten connections. That makes 10 pairs to choose among the 26 possible letters. Here I have a problem understanding how the number of possibilities is obtained.

In the video (around 9:00), the number of configurations is obtained as $\dfrac{26!}{6! 10! 2^{10}}$, and they explain how to get there, but I find it difficult to understand the $2^{10}$ factor in the denominator. For me, the number of configurations looks like a selection of 10 pairs among all the possible pairs, i.e., $\text{possible pairs} = \binom{26}{10} = \dfrac{26!}{2! (26-2)!} = 325$, and choose 10 from them, $\text{possible configurations} = \binom{325}{10} = \dfrac{325!}{10! (325-10)!}$, which is a completely wrong answer, but I don't understand where I got lost.

TL:DR how many 10-pairs are possible in a set of 26 letters?

Please help me understand this, and if you can point me to what to read to get me started in this basic combinatorial analysis, I'll be forever grateful. Many thanks.

$\endgroup$
2
$\begingroup$

Here is one way to do it: arrange the alphabet in such a way that the pairs come first and the unpaired letters last. For example $$\hbox{BGSI . . . UAWEXPTL}$$ means that B and G are paired, S and I are paired, . . . U and A are paired, while W, E, X, P, T and L are unpaired. There are $26!$ ways to do this. However . . .

  • it does not matter which order the letters in a pair are listed, for example, $$\hbox{GBSI . . . AUWEXPTL}$$ would be the same plugboard setting as above. So we must divide by $2^{10}$ to compensate for overcounting.
  • It does not matter in which order the pairs themselves are listed, for example, $$\hbox{SIAU . . . BGWEXPTL}$$ would be the same as above. So divide by $10!\,$.
  • It does not matter in which order the last six letters are listed, for example, $$\hbox{BGSI . . . UAXEPWLT}$$ would be the same as above. So divide by $6!\,$.

This gives the answer you have quoted.

$\endgroup$
  • $\begingroup$ Thanks @david, with your explanation I see it a bit more clear. Could you also tell me what is the problem in my thought process about using $\binom{325}{10}$ to get the number of 10-pairs? $\endgroup$ – LeCoc Jan 8 '15 at 14:00
  • $\begingroup$ You are choosing $10$ of all possible pairs. Your options include things like AZ, BZ, . . . , JZ which are certainly not possible plugboard settings. $\endgroup$ – David Jan 8 '15 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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