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

Combination Question

  1. Jan 16, 2007 #1
    I have a fully solved combination question that I can't seem to follow.

    "How many words of length 4 can be formed if the letters in the word must be in increasing alphabetical order? Note: {A,A,D,E} is but {A,D,A,E} is not"

    The solution is as follows (C denotes choose)

    (26 C 1) + (26 C 1)(25 C 1) + (26 C 2) + (26 C 1)(25 C 2) + (26 C 4) = 23751

    I am having trouble seeing just what this calculation is doing and why it solves the problem (I've only just recently been introduced to permutations and combinations).

    To my understanding, each term in the solution is its own case, but I'm not sure what these cases are.

    Any help in explaining this solution would be appreciated.

    Thanks.
     
  2. jcsd
  3. Jan 17, 2007 #2

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    Can you post the thought process that led to this solution?
     
  4. Jan 17, 2007 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    There are probably several ways to do this. You really need to find some way of making the counting easy.

    You could set up all kinds of difference equations to solve this, but that is hard. You could sum over all possible starting letters, but that is hard.

    How about splitting things up into smaller groups. It is easy to calculate the number of acceptable strings with no repetitions: given any 4 distinct letters, there is precisely one acceptable ordering. Or if you like, there are 26 choose 4 acceptable strings. Now, what about the ones we've yet to count?
     
  5. Jan 17, 2007 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    It isn't a solution they devised, so probably not. But it is breaking it down into cases - the first term counts the strings with one letter in them, and so on.
     
  6. Jan 17, 2007 #5

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    Oh, I hadn't seen the "a" in "I have a fully solved". Sorry.

    I am guessing that the answer is:

    letter1 * (26 - rank(letter1) + 1) * (26 - rank(letter2) + 1) * (26 - rank(letter3) + 1) summed over letter3, then over letter2, then over letter1.
     
    Last edited: Jan 17, 2007
  7. Jan 17, 2007 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Erm, that is not the way to do it. It would contain approximately a thousand or so terms in the sum, wouldn't it? I mean, it is certainly large, and certainly not obvious how to relate it to the given answer which is easy to explain (follow my hint above).
     
  8. Jan 17, 2007 #7

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    I thought my formula would resolve into combinations.
     
  9. Jan 17, 2007 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    If it's correct it will. But can you see an easy way to do that?
     
  10. Jan 17, 2007 #9

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    Point taken. Starting over, with one letter (e.g. AAAA), there are 26 = C(26, 1) combinations.
     
    Last edited: Jan 17, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?