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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.