Results 1 to 9 of 9

Math Help - Enumeration problem

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    204

    Enumeration problem

    hey im having trouble getting started on this question:

    how many strings of at least one and at most three characters from the alphabet have their characters in alphabetical order? repeated characters are allowed and strings such as aab are in alphabetical order.

    i figured with only one character strings, the number of alphabetically-ordered strings is 26, because each string will only have 1 letter, thus n alphabetical order.

    im getting stuck with 2 and 3 characters in the string. i considered starting with each letter in the string, but that was going to take too long. i know it has something to do with commutations/pemutations...
    with 2 character strings, i guess u could do sum of (26-r) from r=0 to 25...cause for the first letter r=0 (ie. a) there are 26 ways, r=1 (b), there are 25 ways etc...but this doesnt have anything to do with commutations/permutations??

    please help!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,913
    Thanks
    1760
    Awards
    1
    \sum\limits_{k = 1}^3 {{26+k-1} \choose k}
    Can you explain why this works?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2008
    Posts
    204
    well that formula looks like the one for unordered repetitions. but where does the sum of come from? and why k from 1 to 3? is that because u have at least 1 and at most 3 strings of characters? how did u separate the alphabetically arranged from the non-alphabetically arranged? im so confused...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,862
    Thanks
    742
    Hello, wik_chick88!

    I had to make lists ... and look for patterns.


    How many strings of at least one and at most three characters
    from the alphabet have their characters in alphabetical order?
    Repeated characters are allowed and strings such as aab are in alphabetical order.
    One-letter strings

    You are right . . . there are {\color{blue}26} possible one-letter strings.



    Two-letter strings

    \begin{array}{cc}& \text{choices for} \\<br />
\text{1st letter} & \text{2nd letter} \\ \hline<br />
a\,\_ & 26 \\ b\,\_ & 25 \\ c\,\_ & 24 \\ \vdots & \vdots \\ y\,\_ & 2 \\ z\,\_ & 1 \end{array}

    Two-letter strings: . 1 + 2 + 3 + \cdots + 26 \;=\;T_{26} \;=\;\frac{26\cdot27}{2} \;=\;{\color{blue}351}



    Three-letter strings

    \begin{array}{cc}aa\_ & 26 \\ ab\_ & 25 \\ ac\_ & 24 \\ \vdots & \vdots \\ ay\_ & 2 \\ az\_ & 1 \end{array} . . \begin{array}{cc}bb\_ & 25 \\ bc\_ & 24 \\ bd\_ & 23 \\ \vdots& \vdots \\ by\_ & 2 \\ bz\_ & 1 \end{array} . . \begin{array}{cc}cc\_ & 24 \\ cd\_ & 23 \\ ce\_ & 22 \\ \vdots & \vdots \\ cy\_ & 2 \\ cz\_ & 1 \end{array} . . \cdots . . \begin{array}{cc}ww\_ & 4 \\wx\_ & 3 \\ wy\_ & 2 \\ wz\_ & 1\end{array} . . \begin{array}{cc}xx\_ & 3 \\xy\_ & 2 \\ xz\_ & 1 \end{array} . . \begin{array}{cc}yy\_ & 2 \\ yz\_ & 1 \end{array} . . \begin{array}{cc}zz\_ & 1 \end{array}


    Reading from the right, we have:

    (1) + (1+2) + (1+2 +3) + \cdots + (1+2+3+\cdots+26)

    . . = \;T_1 + T_2 + T_3 + \cdots + T_{26} \;=\;\frac{26\cdot27\cdot28}{3!} \;=\;{\color{blue}3276} 3-letter strings



    Answer: . 26 + 351 + 3276 \;=\;\boxed{3653}

    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,913
    Thanks
    1760
    Awards
    1
    Quote Originally Posted by wik_chick88 View Post
    well that formula looks like the one for unordered repetitions. but where does the sum of come from?
    Exactly, we do use unordered repetitions to solve these problems.
    Let me give you another problem to demonstrate the concept.
    How many way can we select five letters from the alphabet allowing repetitions: {{5+26-1} \choose {5}}. Correct?
    If you are given any collection for five letters, say any five Scrabble pieces, you can always arrange those pieces in alphabetical order. Can you not?
    Therefore, we have just counted the number of five letters strings appearing in alphabetical order.
    Now the sum is for one, two, or three strings.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Apr 2008
    Posts
    204
    ok. im pretty sure the question is ordered ie. the first letter has to stay the first letter. so i made the lists, saw the patterns and worked out how many strings would be possible. BUT the next question is how many strings of at least one and at most n characters from the alphabet have the characters in alphabetical order? you used T1, T2,...,T26 in your answer what is the definition of Tn? Thanks for all your help!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,913
    Thanks
    1760
    Awards
    1
    Quote Originally Posted by wik_chick88 View Post
    ok. im pretty sure the question is ordered ie. the first letter has to stay the first letter. so i made the lists, saw the patterns and worked out how many strings would be possible. BUT the next question is how many strings of at least one and at most n characters from the alphabet have the characters in alphabetical order? you used T1, T2,...,T26 in your answer what is the definition of Tn? Thanks for all your help!
    Well of course they are ordered!
    But the point here is that we count the number of unordered selections each of which we can then in turn order.
    The selection <B,A,L,L,O,O,N> can be ordered into ABLLNOO.
    That selection is one of {{7+26-1} \choose {7}}=3365856 possible selections of seven choices of letters allowing repeats.
    But that is also the number of seven letter ‘words’ having their letters is alphabetical order.

    Thus the answer to the second part, “n characters from the alphabet have the characters in alphabetical order”, is {{n+26-1} \choose {n}}.
    Now you add k=1,..,n.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Apr 2008
    Posts
    204
    thanks guys for all ur help now i understand what to do and i can explain it in my own words!! THANKS!!!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Mar 2008
    Posts
    13
    I stil don't understand what T1 + T2 + T3... is suppose to stand for and thus don't understand how you came to the conclusion that it equals 26x27x28/3!

    \

    If possible can you please explain this!
    Thanks Soroban!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Enumeration question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 14th 2009, 08:34 PM
  2. Enumeration problems
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 12th 2009, 02:08 AM
  3. Replies: 0
    Last Post: April 11th 2009, 08:09 AM
  4. enumeration problem solving question
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: September 10th 2008, 03:37 PM
  5. enumeration
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 23rd 2005, 03:54 PM

Search Tags


/mathhelpforum @mathhelpforum