Finding the Number of Simple Substitution Ciphers with No Fixed Points

[moo5003]

Homework Statement

Question: How many simple substitution ciphers are there where no point is fixed (ie: no letter is mapped to itself)?

EDIT: Incase the termonoligy is different, a simple substitution cipher is a mapping where the plaintext in english is encoded so that every letter is mapped to a different letter.

IE:
a maps to Z
b maps to S
c maps to K
etcetcetc

thus abc plaintext is mapped to ZSK.

The Attempt at a Solution

So, I did a few examples to see if I could get some insight into the problem:
1 Letter = 0 mappings
2 Letters = 1 mapping
3 Letters = 2 mappings
4 Letters = 9 mappings
5 Letters = 44 mappings
I stopped here

While I found the reason for the complexity of determining this number I didn't come across any way to do it in general for 26 letters (for English). I know it has to be above (n-1)! and below n! for n letters but other then that I'm unsure.

I'm thinking I can just brute force it using algebraic notation, for example in the case of 4 letters I counted the mappings:
1 - 4cycle and with 4 letters there are 6 distinct combinations
2 - 2cycles and with 4 letters there are 3 distinct combinations

But, with 26 letters the number of different cycle combinations becomes cumbersome.

Any guidance would be appreciated.

 

[HallsofIvy]

Here's the way I would approach it: There are n! ways to permute n letters. But (n-1)! of them "fix" the first letter. Of the remaining, (n-2)! fix the second letter, of the remaining (n-3)! fix the third letter, etc. There are n!- ((n-1)!+ (n-2)!+ ...+ 2+ 1) permutations that do not fix any letter.

 

[moo5003]

I'm not sure I follow, when you say (n-1)! is the number of ways to fix the first letter does this allow more then the first letter to be fixed?

ie: For 5 letters
1 maps to 1
2 maps to 2
3 maps to 3
4 maps to 4
5 maps to 5

Would be counted in your (n-1)!.

Now when you count the ways to fix the second letter I lose track of where you go. How did you count (n-2)! ways of fixing the second letter?

 

[Dick]

That's a FUN problem. Try this. Call s(n) the number of cyphers containing n elements with no element fixed. Can you figure out a recursion formula to calculate s(n) assuming you know s(k) for k<n? If you have an (n-1)-cypher with no fixed elements how many ways can you extend it to an n-cypher with no fixed elements by just changing one element of the (n-1)-cypher? If you think harder about it you'll realize that this isn't all of the n-cyphers. You could also take an (n-1)-cypher with a single element fixed and change to an n-cypher. How many n-1-cyphers are there with a single element fixed? I haven't figured out how to 'sum' the resulting recursion relation and get to n=26 without computing all of the lower ones, though.

 

[moo5003]

Ok, I think I have my recursion formula.
S(n) = Number of maps with no fixed points and n letters
Define: S(0) = 1 so the recursion looks nice, or consider it the empty mapping
aCb = a choose b, ie: 26C2 = 325

S(n) = n! - ( nC1*S(n-1) + nC2*S(n-2) + nC3*S(n-3) + ... + nC(n-1)*S(1) + nCn*S(0) )

n! is the total mappings, nCi*(S-i) are the number of mappings with i fixed points.

So is the next step to work out all of these for n=26?

 

[Dick]

That's one way. Kind of a pain to do by hand. Easy if you've got a computer. If you think about the approach I outlined you can get an easier formula. S(n)=(n-1)*(S(n-1)+S(n-2)). That works nicely until the numbers start getting big. I turns out (I did some research) there is even a nonrecursive relation you can derive with inclusion-exclusion arguments. There's actually literature on this problem. A permutation with no fixed point is called a 'derangement'. Do they actually want you to calculate the number? It's got a lot of digits. Turns out it's very close to 26!/e, believe it or not.

 

[moo5003]

I see your extension idea, I was a little confused but now I think I understand. There are n-1 ways to extend S(n-1) into the range of S(n) but this means that any cycle including the new letter cannot be a 2-cycle ie: you need to also include extensions from one fixed point with n-1 letters. There are (n-1)S(n-2) mappings that you must add giving you (n-1)(S(n-1)+S(n-2)). I agree I like your formula better :P.

 

[Dick]

You're pretty good at this. Did you try an internet search for 'derangement'? It's actually pretty interesting. I liked the bit on mathworld where you can show the count is the incomplete gamma function of (n-1,-1) divided by e. And there's an even simpler recursion. S(n)=n*S(n-1)+(-1)^n. I haven't checked all the details on all of this, but there's more than one way to skin this cat. Your first recursion was actually the first one I figured out. Thanks for the diversion!

 

[moo5003]

I read the wikipedia and wolfram entries on it, I'm still working through the details on how they got their closed form (for n>=2) though I'm sidetracked as I want to keep up with the class I'm following independently in cryptography.

ie: Learning how to program some of the problems.