Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Possible Combinations when Distributing Items Unevenly

Date: 05/24/2004 at 15:40:54
From: Jessica
Subject: Combinations of 20 objects for 5 children

There are 20 distinct toys to be handed out to 5 children.  How many 
possible ways are there to hand them out if two children each get 7 
toys and three children get 2 toys each?

I know that there are 10 combinations of how to arrange what child 
gets how many presents (5!/2!3!), but it's the rest I'm stuck on.  I
tried [C(20 7)+ C(20 7) + C(20 2) + C(20 2) + C(20 2)] * 10, but the
number is far too high.  Can you help?



Date: 05/24/2004 at 16:23:37
From: Doctor Vogler
Subject: Re: Combinations of 20 objects for 5 children

Hi Jessica,

What you need are the multinomial coefficients.  These are a 
generalization (or an extension) of the binomial coefficients (also
known as combinations, or n-choose-r).

If you have n objects, and you want to put them all into k boxes, so
that box i (for i=1,2,...k) gets a_i objects (which means that the sum
of all of the a_i's has to be n), then you can do this in

                 k!
  -------------------------------
  (a_1)!*(a_2)!*(a_3)!*...*(a_k)!

ways.  In your case, you have n=20 objects (toys), and k=5 boxes 
(children), who get a_1 = 7, a_2 = 7, a_3 = 2, a_4 = 2, a_5 = 2
objects (notice that 7+7+2+2+2 = 20), so there are

     20!
  ----------
  7!7!2!2!2!

ways to do this.

To justify this, consider that we will arrange the n objects in a 
line.  Then the first box (or child) gets the first a_1 objects, the
second box gets the next a_2 objects, and so on.  There are n! ways to
arrange the objects in a line, but then we can rearrange the first a_1
objects without changing the outcome, and we can rearrange the next
a_2 objects, and so on.

Finally, just as the binomial coefficients (n-choose-r) come up in the
expansion of (x + y)^n, so too the multinomial coefficients come up in
the expansion of (x + y + z)^n (or with more variables).  For more
info on this, see

  Multinomial Coefficients
    http://mathforum.org/library/drmath/view/64616.html 

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/