1
$\begingroup$

Imagine there are $7$ cells and $7$ balls.

How many patterns are there with $3$ balls in one cell and $4$ balls in another cell.

The Books answer is $ 7 \times 6 \times \binom{7}{3} $

I'm wondering what's wrong in my approach. I try to split up the problem into several tasks.

(1) I first need to choose the two bins that I will put balls in. $\binom 7 2$ ways to do this.

(2) I then need to select 3 balls to put in the first bin. $\binom 7 3$ ways to do this.

But then I am done, since the other 4 necessarily have to go in the 2nd bin. What am I doing wrong?

Just so that I'm clear on the approach could someone attempt the below problem aswell so that I can see how you do it with more then 2 bins.

Consider the same question but with the goal of getting the 7 balls into 3 different cells with a 3-2-2 split.

Edit : It seems I wasn't counting the fact that the 3 balls could go into either bin. I've attempted a solution for the second question keeping this in mind but I still got it wrong.

(1) : Pick 3 cells . $\binom 7 3$ ways to do this.

(2) : Pick 3 balls $\binom 7 3$ ways to do this.

(3) : Choose which of the 3 cells these balls go into. 3 ways to do this.

(4) : Choose 2 balls from the remaining 4. $\binom 4 2$ ways to do this.

(5) : Pick which of the 2 cells these balls go into. $2$ ways to do this.

That should be it since the remaining 2 balls automatically go into the last cell.

Hence, the answer should be $35 \times 35 \times 3 \times 6 \times 2 = 44100$

However the answer in the book says it's 22050.

What's wrong with this?

$\endgroup$
  • $\begingroup$ In questions like these, it should be mentioned whether the balls can be distinguished from one another and whether the cells can be distinguished from one another. Given the book's answer, it seems that the balls and the cells are all labeled and distinguishable. $\endgroup$ – JMoravitz Sep 21 '15 at 3:01
2
$\begingroup$

For the first question, as you have figured out you need to break it up as the following:

  • Pick which cell will get $4$ balls
  • Pick which cell will get $3$ balls
  • Pick which $4$ balls to send to the cell that we picked in step 1

for a total of $7\cdot 6\cdot \binom{7}{4}$ number of ways. This is of course equivalent to having picked the two bins simultaneously followed by picking which bin of the two was going to house the larger number of balls followed by picking how to distribute the balls.

$7\cdot 6\cdot \binom{7}{4}=\binom{7}{2}\cdot 2\cdot \binom{7}{4}=7\cdot 6\cdot \binom{7}{3}=\binom{7}{2}\cdot 2\cdot \binom{7}{3}$


As for the second question, break it up as the following:

  • Pick which cell will get $3$ balls
  • Pick which two cells will get $2$ balls
  • Pick which three balls go into the cell picked in step 1
  • Temporarily defining an order, (since the cells are distinguishable), pick which two balls go into the "lesser" cell of the two that were picked in step 2

We are allowed to pick the "lesser" cell since the cells are distinguishable. If they were not, then this would be an invalid step. By an order, I mean to say that if the cells were labeled something like a,b,c,$\dots$, then the "lesser" cell would be the one that appears first in alphabetical order.

There are then $\binom{7}{1}\binom{6}{2}\binom{7}{3}\binom{4}{2}\binom{2}{2} = 22050$ number of ways of accomplishing this.

Your mistake was that you double-counted.

Suppose the cells are labeled a,b,$\dots$ and the balls are labeled 1,2,$\dots$.

Using the steps defined in your proposed solution, the sequence of choices: abc,123,a,45,b gives the same result as abc,123,a,67,c as they both end up with cell a containing 123, cell b containing 45, and cell c containing 67.

Similarly, for every other sequence of choices, there is exactly one other dual sequence of choices that gives the same result, so it is as though you counted every possibility twice. Dividing by two corrects this and gives the correct answer.

$\endgroup$
  • $\begingroup$ Right, I didnt actually know that you could just decide like that on each step which cell wil get what number of balls. As you probably noticed I went out of my way to sort of avoid doing that. Thanks, this makes much more sense. $\endgroup$ – Exc Sep 21 '15 at 3:38
0
$\begingroup$

I think your approach is right except that in step 2 you could put the 3 balls in the first bin OR put the 3 balls in the second bin, so you really have $2 \cdot \binom{7}{3}$ ways to do it. This should then agree with the answer in the book.

$\endgroup$
  • $\begingroup$ I've edited my question to include an answer to the second question as well. Could you take a look at that? $\endgroup$ – Exc Sep 21 '15 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.