2
$\begingroup$

I am having a bit of trouble understanding which combinatorial methods to use for this problem. I've actually resorted to listing some of these scenarios out (brute force) to get my solution. I would like some advice on counting methods (and possibly references to texts on counting methods) in order to solve problems like this WITHOUT using brute force.

Say I have 6 similar balls and 9 distinguishable boxes labeled A - I. I want to distribute my balls as follows:

  • box A gets 1 ball
  • box B gets 2 balls
  • the remaining three balls can be distributed any way amongst the leftover boxes


There are 6 ways I can give box A a ball. There are $_{5}C_{2}=10$ ways for box B to get two balls. Now I have 3 balls left and 7 boxes (C through I) left. I can put all three balls in box C or box D, etc in 7 different ways. I can chose to put one ball in one box and two balls in one box in 42 (and I literally listed each way on paper to figure this one out). Finally, I can place 1 ball in each of three boxes in $_{7}C_{3}$ ways.

This leads me to my solution of: $6 \cdot 10 \cdot 35 + 6 \cdot 10 \cdot 42 + 6 \cdot 10 \cdot 7 = 5,040$ ways for box A to get 1 ball, box B to get 2 balls and the remaining C, D, E, F, G, H, I boxes to get the remaining three balls in any way.

My questions:
(1) Am I correct that there are 42 ways for 3 balls to be split amongst 7 boxes if one box gets one ball and another box (any box) gets two balls? If so, how can I enumerate this WITHOUT using brute force?
(2) Is it correct that I added three scenarios? That is, A getting 1 ball, B getting 2 balls, and one of the remaining 7 boxes getting all three can be done (6)(10)(7) ways. I added this amount to the other two possible outcomes for the remaining 7 boxes.

$\endgroup$
3
  • 2
    $\begingroup$ If the balls are identical, then A and B can only be done in one way. Three balls in $6$ boxes is standard Stars and Bars. I recommend you read the Wikipedia article on this. Later, Wikipedia The Twelvefold Way may be useful, tougher going. $\endgroup$
    – André Nicolas
    Jan 21, 2015 at 18:08
  • $\begingroup$ If the balls are indistinguishable, it doesn't matter which you put in boxes A&B - so just put 1 in A and 2 in B before you start. Then you just have to partition the remaining 3 balls into the 7 remaining boxes, ${7+3-1 \choose 3}=84$ $\endgroup$
    – Joffan
    Jan 21, 2015 at 18:08
  • 1
    $\begingroup$ Notice that $35+42+7 = 84$, so you got the correct total number of ways to distribute the last three balls. Your error is counting the first three balls as if they were distinguishable after you said they were not. $\endgroup$
    – David K
    Jan 21, 2015 at 21:09

1 Answer 1

Reset to default
0
$\begingroup$

Since balls are indistinguishable, you only need to worry about the number of balls in a bin. You need to distribute 3 balls in 7 distinct bins. One way of doing it is by partitioning the number 3: $$ 3 =a_1 +a_2 + \ldots a_7 $$ You can either have (a) 3 balls in 1 bin, (2) 2 balls in 1 and 1 ball in the 2nd bin, (3) 1 ball in 3 bins. Clearly there are 7 ways for (a): $3=3+0+ \ldots 0=0+3 + \ldots 0$ etc, $7 \cdot 6$ for (b), since all the bins are distinct and $\binom{7}{3}$ for (c). Now sum them up: $\binom{7}{1} + 42 + \binom{7}{3} = 7 + 42 + 35 = 84$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .