Results 1 to 3 of 3

Math Help - counting

  1. #1
    sss
    sss is offline
    Junior Member
    Joined
    Sep 2008
    Posts
    27

    counting

    how many different strings can be made from the letters on orono using some or all of its letters

    I know how to find the strings with all letters : 5!/3! but how do I find out the stings of different lengths?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello sss
    Quote Originally Posted by sss View Post
    how many different strings can be made from the letters on orono using some or all of its letters

    I know how to find the strings with all letters : 5!/3! but how do I find out the stings of different lengths?
    It doesn't take long to work out the number for each different length and add them up:

    As you say, length 5: \frac{5!}{3!} = 20

    Length 4 can contain 3 or 2 o's.

    • With 3 o's + 1 other, there is a choice 2 for the other letter, so the number is 2 \times\frac{4!}{3!}=8.
    • With 2 o's both the other letters must be used, so that's \frac{4!}{2!}=12.


    Length 3:

    • 3 o's: 1
    • 2 o's + 1 other: 2\times \frac{3!}{2!}=6
    • 1 o + 2 others: \frac{3!}{1!}=3

    Length 2:

    • 2 o's: 1
    • 1 or 0 o's: {^3P_2} = 6

    Length 1: 3

    So I reckon that's 20+8+12+1+6+3+1+6+3=60.

    That's a nice round number so I don't know if anyone knows of a quicker method?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Grandad View Post
    Hello sssIt doesn't take long to work out the number for each different length and add them up:

    As you say, length 5: \frac{5!}{3!} = 20

    Length 4 can contain 3 or 2 o's.

    • With 3 o's + 1 other, there is a choice 2 for the other letter, so the number is 2 \times\frac{4!}{3!}=8.
    • With 2 o's both the other letters must be used, so that's \frac{4!}{2!}=12.


    Length 3:

    • 3 o's: 1
    • 2 o's + 1 other: 2\times \frac{3!}{2!}=6
    • 1 o + 2 others: \frac{3!}{1!}=3...6

    Length 2:

    • 2 o's: 1
    • 1 or 0 o's: {^3P_2} = 6

    Length 1: 3

    So I reckon that's 6
    +1+6+3=60" alt="20+8+12+1+6+6+1+6+3=60" />. ...63

    That's a nice round number so I don't know if anyone knows of a quicker method?

    Grandad
    A little slip in arithmetic above...

    I don't have a real shortcut, but I can't resist pointing out that the "easy way" if you are familiar with generating functions is to find the exponential generating function.

    I.e., let a_r be the number of words of length r and define g(x) = \sum_{r=0}^{\infty} a_r x^r / r!. Then it's easy (if you know how) to see that

    g(x) = (1 + x)^2 (1 + x + x^2 / 2! + x^3 / 3!)

    which on expansion yields

    g(x) = 1 + 3 x + 7 x^2 / 2! + 13 x^3/3! + 20 x^4/4! + 20 x^5/5!

    From this you can read off the number of words of length 1-5: 3, 7, 13, 20, 20.

    This isn't much help for someone who doesn't know anything about generating functions, I guess, except it may give an incentive to learn.

    Personally, I think generating functions are neat-- I guess you can tell that.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. counting 1
    Posted in the Statistics Forum
    Replies: 1
    Last Post: September 8th 2011, 08:01 AM
  2. Counting
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 9th 2010, 04:34 AM
  3. Counting
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 9th 2010, 05:19 PM
  4. help on Counting
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 25th 2009, 08:51 AM
  5. Counting
    Posted in the Algebra Forum
    Replies: 2
    Last Post: August 10th 2009, 05:32 PM

Search Tags


/mathhelpforum @mathhelpforum