Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Simple Substitution Ciphers

  1. Feb 24, 2009 #1
    1. The problem statement, all variables and given/known data

    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.

    3. 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.
     
    Last edited: Feb 24, 2009
  2. jcsd
  3. Feb 24, 2009 #2

    HallsofIvy

    User Avatar
    Science Advisor

    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.
     
  4. Feb 24, 2009 #3
    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?
     
  5. Feb 24, 2009 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
    Last edited: Feb 24, 2009
  6. Feb 24, 2009 #5
    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?
     
  7. Feb 24, 2009 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  8. Feb 24, 2009 #7
    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.
     
  9. Feb 24, 2009 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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!
     
  10. Feb 25, 2009 #9
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook