kitchen table math, the sequel: help desk - balls in boxes

Thursday, April 21, 2011

help desk - balls in boxes

from Art of Problem Solving's Introduction to Counting and Probability:
5.16 How many ways are there to put 4 balls in 3 boxes if:
(b) the balls are distinguishable but the boxes are not.
I don't understand the part of the solution that explains how many ways you could put 2 balls in one box, 2 balls in another box, and 0 balls in a third box:
(2,0,0): There are 4C2 = 6 ways to choose the balls for the first box, and the remaining go in the second box. However, the two pairs of balls are interchangeable, so we must divide by 2 to get 6/2 = 3 arrangements.
To me, it seems like there would have to be 6 ways to choose 2 balls from balls 1, 2, 3, and 4 for the first box:

1,2
1,3
1,4
2,3
2,4
3,4

What am I missing?

For the option of (2,1,1), the solution is 6, not 3:
There are 4C2 = 6 options for picking the two balls to go in one box, and each of the other two balls goes into its own box.
I don't see how (2,0,0) is different from (2,1,1) when the boxes are indistinguishable.

Introduction to Counting & Probability (The Art of Problem Solving)

6 comments:

Allison said...

"Boxes are indistinguishable" means something very very specific: the boxes are physically distinct from each other, but the boxes aren't labelled.

So their order doesn't matter. That's the important point.

Occupancy numbers, the number of balls in a box, are not the same as distinguishability or indistinguishability.

Let
[0] be a box with 0 balls,
[1] be a box with 1 ball,
[2] be a box with 2 balls.

If the order mattered, then

[0] [1] [2]
is a different solution than
[1] [2] [0].

But when order doesn't matter, then
the two above solutions are the same solution--one box has 0 items, one box has 1 item, one box has 2 items.

However,
[2] [0] [0]
means one box has 2, and two boxes have zero.

That's a completely different solution from
[2] [1] [1]
where one box has 2 balls, and 2 boxes have 1 ball.

Now, I don't understand the part of the solution where you typed (2,0,0). Did you mean (2,2,0) ?

Yes, there are six ways of put 2 balls in the "first" box, like you said:

[ball 1, ball 2],
[ball 1, ball 3],
...
[ball 3, ball 4]

but what does "the second" box look like?

so when you write it out, the answer is the second box looks a lot like the first, right? Because there is no "first box".
[ball 1, ball2] [ball 3 ball 4] [0]
is the same as
[ball 3 ball 4] [ball 1 ball 2] [0].

So when you try to write out all 6 options, you'll see that three of them match another one already on your list, and that leaves only 3 options, not 6.

Allison said...

(cont)

But when you have 2 and 1 and 1,
it's true that the two single occupancy boxes are the same, but the total number of ways of putting balls into those boxes is different than the ways of putting 2 balls into those 2 boxes.

[ball 1 ball2] [ball 3][ball4]
is the same as
[ball 1 ball2] [ball 4] [ball 3], yes.
but like you said, there are 6 ways of putting 2 balls in the "first" box, and [ball 4] [ball 3] doesn't change that.

Catherine Johnson said...

[ball 1, ball2] [ball 3 ball 4] [0]
is the same as
[ball 3 ball 4] [ball 1 ball 2] [0]


ah hah!

Thank you!!

I don't 'understand' this aspect of combinations at all ---- though I'm starting to "get used to it."

I find the idea that 6C2 is the same as 6C4 is pretty astounding at this point.

Catherine Johnson said...

Thanks, Allison!

I **really** appreciate your taking the time to write out this explanation.

I wasn't going to come to it on my own---

Anonymous said...

6C2 vs. 6C4

Image you have six balls (red, orange, yellow, green, blue, and purple, for example). You also have a box.

6C2: I have six balls, and I am choosing which two balls to put in the box.

6C4: I have six balls, and I am choosing which four to leave out of the box.

Thus, the combination "I put red and orange in the box," is the same way of splitting up the balls as "I leave yellow, green, blue, and purple out of the box." Counting the ways to put two in the box is the same as counting the ways to leave four out of the box.

Catherine Johnson said...

Anonymous --- THANK YOU

I can't tell you all how helpful this is for me --- I so appreciate your help.