seemingly basic combinations problem - Math Help Forum

$Math Help Forum$

$Go Back$		Math Help Forum > University Math Help > Discrete Mathematics, Set Theory and Logic
$Reload this Page$ seemingly basic combinations problem

Download MHF Flyer

Mark Forums Read

$Reply$

#1

$Old$ November 2nd, 2009, 08:16 PM

lightbeam $lightbeam is offline$

Newbie

Join Date: Nov 2009

Posts: 2

Thanks: 0

Thanked 0 Times in 0 Posts

$lightbeam is on a distinguished road$

$Default$ seemingly basic combinations problem

There are M letters. N>M. How many N letter "words" include all M letters?

$Reply With Quote$

Advertisement

#2

$Old$ November 13th, 2009, 03:56 PM

lightbeam $lightbeam is offline$

Newbie

Join Date: Nov 2009

Posts: 2

Thanks: 0

Thanked 0 Times in 0 Posts

$lightbeam is on a distinguished road$

$Default$

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.

$Reply With Quote$

$Reply$

« Probability | Top | Prove my mathematics induction, trigonometry »

Thread Tools
$Show Printable Version$ Show Printable Version $Email this Page$ Email this Page
Display Modes
$Linear Mode$ Linear Mode $Hybrid Mode$ Switch to Hybrid Mode $Threaded Mode$ Switch to Threaded Mode

Posting Rules
You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are Off

Forum Jump

All times are GMT -7. The time now is 07:34 PM.

your link here Sponsors

rv solar, e-learning,

Math Help Forum is a community of maths forums with an emphasis on maths help in all levels of mathematics.
Register to post your math questions or just hang out and try some of our math games or visit the arcade.