Results 1 to 2 of 2

Math Help - seemingly basic combinations problem

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    2

    seemingly basic combinations problem

    There are M letters. N>M. How many N letter "words" include all M letters?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2009
    Posts
    2
    Quote Originally Posted by lightbeam View Post
    There are M letters. N>M. How many N letter "words" include all M letters?
    A nice solution provided by my neighbor relies on the "inclusion-exclusion" principle. Apply it to the intersection of the M sets A_i={words that include the i'th letter}.

    The answer is
    M^{N} - \binom{M}{1} (M-1)^N + \binom{M}{2} (M-2)^N - ... \binom{M}{M-1} (M-(M-1))^N
    Note the alternating signs.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: November 3rd 2010, 09:07 PM
  2. 5 Basic tastes, how many combinations?
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 17th 2010, 06:03 AM
  3. Basic combinations question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 23rd 2009, 12:55 AM
  4. Basic combinations?
    Posted in the Statistics Forum
    Replies: 2
    Last Post: September 16th 2009, 10:05 AM
  5. Help with a seemingly simple math problem!
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: August 14th 2007, 11:01 PM

Search Tags


/mathhelpforum @mathhelpforum