1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
    Staff Emeritus
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Simple Substitution Ciphers
Loading...