Number of ways to fill 3 boxes with 5 balls

[andyrk]

What are the number of ways in which 3 different boxes can be filled with 5 different balls so that one box gets 3 balls and the other two get 1 ball each? Each box has the capacity to hold 5 balls at most.

The answer to this is 5!/(3!1!1!) x 1/2! x 3! = 60

But when I do it, I think of it this way- (Number of ways to chose 3 balls out of 5) x (Number of ways to chose 1 ball out of 2) x (Number of permutations of boxes) = C(5,3) x C(2,1) x 3! = 5! = 120.

But this is wrong as one can easily see. So how do I go about the right way?

 

[nuuskur]

Rule of product
First, determine how many possibilities there are to pick 3 different balls for one box - C_5,3 - 10 ways.
Apply rule of product - for 3 different boxes: 30, as for each individual box there are 10 ways.
The remaining 2 balls just have 2 possibilities for each previous setup you considered - 30 x 2 = 60.

Your method almost hits home, but when you calculate permutations of boxes, you are counting the same thing too many times. Not ...x 3!, but just .. x 3. It is here where you violate the rule of product.

3! means something like this: You have calculated all the possibilities to set up 3 boxes as requested, BUT now you don't merely count them all together, but you are also considering their ordering and that is not demanded in the problem statement.

Also, do you understand why the word "different" is used to describe the balls and boxes?

 

[andyrk]

Rule of product
First, determine how many possibilities there are to pick 3 different balls for one box - C_5,3 - 10 ways.
Apply rule of product - for 3 different boxes: 30, as for each individual box there are 10 ways.
The remaining 2 balls just have 2 possibilities for each previous setup you considered - 30 x 2 = 60.

Your method almost hits home, but when you calculate permutations of boxes, you are counting the same thing too many times. Not ...x 3!, but just .. x 3. It is here where you violate the rule of product.

3! means something like this: You have calculated all the possibilities to set up 3 boxes as requested, BUT now you don't merely count them all together, but you are also considering their ordering and that is not demanded in the problem statement.

Also, do you understand why the word "different" is used to describe the balls and boxes?

Oh yeah. I got that now. Thanks for the help. But could you explain how it got represented in the form 5!/(3!1!1!) x 1/2! x 3! = 60? I have the way to answer the question but I am just concerned about how it got represented like that?

 

[andyrk]

Also, on your reasoning as to why 3 would be used in place of 3!, shouldn't it be 3!? That is because after we have selected the balls we now need to select the boxes for them. So let's label the set of 3 balls we selected as A and the other one ball as B and the last one ball as C. Then A has 3 options to be put and B has 2 options to be put and finally C is left with only 1 option. So shouldn't it be 3 x 2 x 1 = 3!? and not 3 in the end and so shouldn't the answer be 120?

 

[Stephen Tashi]

So let's label the set of 3 balls we selected as A and the other one ball as B and the last one ball as C.

Did you mean "the set of 3 boxes" ?

 

[Stephen Tashi]

Label the balls as 1,2,3,4,5 and the boxes as A,B,C.

The assignments
A: 1,2,3 B: 4 C:5
A: 1,2,3, C: 5 B:4
are not distinct assignments. They would be counted as distinct assignments if you imagine picking distinct groupings of balls and laying the groups out in order on table ( 3 balls, 1 ball and 1 ball) and then assigning the boxes to the groupings. The two groups of 1 ball cause a problem in that method of counting. You could correct your answer by dividing by (2!).

$C_{n1,n2,n3}^{N} = C_{n1}^N C_{n2}^{N-n1} C_{n3}^{N-n1-n2}$ so your method is the same approach as the book's answer. The book's answer contains the correction factor $\frac{1}{2!}$.

 

[andyrk]

Did you mean "the set of 3 boxes" ?

No, I meant set of of 3 balls only.

Label the balls as 1,2,3,4,5 and the boxes as A,B,C.

The assignments
A: 1,2,3 B: 4 C:5
A: 1,2,3, C: 5 B:4
are not distinct assignments. They would be counted as distinct assignments if you imagine picking distinct groupings of balls and laying the groups out in order on table ( 3 balls, 1 ball and 1 ball) and then assigning the boxes to the groupings. The two groups of 1 ball cause a problem in that method of counting. You could correct your answer by dividing by (2!).

$C_{n1,n2,n3}^{N} = C_{n1}^N C_{n2}^{N-n1} C_{n3}^{N-n1-n2}$ so your method is the same approach as the book's answer. The book's answer contains the correction factor $\frac{1}{2!}$.

But A:1,2,3 B: 4 C:5
and A:1,2,3 B: 5 C:4
are distinct assignments, right? So That's the reason I included 3 x 2 in my answer and not just 3. That's because, the balls 1,2,3 (labelled as set A in my convention) have 3 choices of boxes and then ball 4 (set B in my convention) has 2 boxes to chose from and finally ball 5 (set C in my convention) is left with only 1 box to chose from. So the numbers of ways to populate the boxes such in the ratio of 3:1:1 would be C(5,3) (Number of ways to chose 3 balls from 5) x C(2,1)(Number of ways to chose 1 ball from the remaining 2) x 3! (number of ways to populate/chose the boxes) = 120. But this seems to differ when I compare it with the answer, i.e. 60, which makes me confused as to where did I go wrong?

 

[Stephen Tashi]

But A:1,2,3 B: 4 C:5
and A:1,2,3 B: 5 C:4
are distinct assignments, right?

Yes, they are distinct assignments. However the list:

A:1,2,3 B:4 C:5
A:1,2,3 C:4 B:5
A:1,2,3 C:5 B:4
A:1,2,3 B:5 C:4

contains redundant assignments.

If we have put the balls on a table as (1,2,3) (4) (5) and assign the boxes A,B,C to these groups each assignment of boxes is a distinct way of putting the balls in the boxes.

However when we consider the grouping (1,2,3)(5)(4) and assign the boxes to groups, we duplicate assignments that were made in the previous step.

 

[andyrk]

Right. But my answer doesn't include duplicate answers. The 3! is there because of a reason which I mentioned in Post #7. It doesn't include any duplicate assignments.

 

[Stephen Tashi]

In your notation and with your method, some possibilities are:

Groups of balls A = {1,2,3} , B = {4}, C = {5}
Assignment of groups: A in Box 1, B in Box 2, C in Box 3

Groups of balls A = {1,2,3}, B = {5}, C = {4}
Assignment of groups: A in Box 1, B in box 3, C in Box 2

Those two assignments are the same.

 

[andyrk]

Why are they the same? Each ball is different, each box is different so shouldn't the two assignments be different and not the same? Also, how does this account for the fact that 3 should be used instead of 3 x 2 x 1 = 3! in the end of the answer?

 

[Stephen Tashi]

Why are they the same?

In each case Box 2 contains ball 4 and Box 3 contains ball 5.

 

[andyrk]

You put it the wrong way. What I meant was that why is A = 1,2,3 B = 4 and C = 5 the same as A = 1,2,3 B = 5 and C = 4?
Here A,B,C are boxes and 1,2,3,4,5 are balls.

 

[Stephen Tashi]

You put it the wrong way. What I meant was that why is A = 1,2,3 B = 4 and C = 5 the same as A = 1,2,3 B = 5 and C = 4?

Those groupings of balls are not the same. I didn't say they were the same.

 

[andyrk]

Those groupings of balls are not the same. I didn't say they were the same.

Okay. But that was what I essentially wanted to confirm. And as it turns out that they are different then what makes the answer have 3 in the end and not 3 x 2 = 3! ??

 

[Stephen Tashi]

Okay. But that was what I essentially wanted to confirm. And as it turns out that they are different then what makes the answer have 3 in the end and not 3 x 2 = 3! ??

The assignment of the boxes to the 3 groups of balls must be done for each of those groupings. Assignments of boxes to one grouping of balls duplicates situations reached in assignments of boxes to the other grouping of balls.

 

[andyrk]

The assignment of the boxes to the 3 groups of balls must be done for each of those groupings. Assignments of boxes to one grouping of balls duplicates situations reached in assignments of boxes to the other grouping of balls.

But my method doesn't assign boxes to only one group of balls. Its assigns boxes to all group of balls. Then where is the problem?

 

[Stephen Tashi]

But my method doesn't assign boxes to only one group of balls. Its assigns boxes to all group of balls. Then where is the problem?

If you can't see that from post #10, try writing out what your method does for a simpler problem where two boxes have the same number of balls in them.

 

[andyrk]

Okay. So we have 2 different boxes and 4 different balls. And we have to put 2 in each of them. They number of ways to do so would be: C(4,2) (Number of ways to select 2 balls out of 4) x C(2,1) (Number of ways to assign a box to anyone group of balls selected) = 12 ways. That was my method for the original problem too.

 

[Stephen Tashi]

Write out the actual assignments. For example 2 balls in 2 boxes with 1 ball in each box.

Balls {1,2}

Groupings
Grouping 1: A= {1} B = {2}
Grouping 2: A = {2} B = {1}

Box Assignments to Groupings:
Box 1 to Grouping 1 A, Box 2 to Grouping 1 B: result is ball 1 in Box 1, ball 2 in Box 2
Box 2 to Grouping 1 A, Box 1 to Grouping 1 B: result is ... etc.
Box 1 to Grouping 2 A, Box 2 to Grouping 2 B:
Box 2 to Grouping 2 A, Box 1 to Grouping 2 B:

 

[andyrk]

Write out the actual assignments. For example 2 balls in 2 boxes with 1 ball in each box.

Balls {1,2}

Groupings
Grouping 1: A= {1} B = {2}
Grouping 2: A = {2} B = {1}

Box Assignments to Groupings:
Box 1 to Grouping 1 A, Box 2 to Grouping 1 B: result is ball 1 in Box 1, ball 2 in Box 2
Box 2 to Grouping 1 A, Box 1 to Grouping 1 B: result is ... etc.
Box 1 to Grouping 2 A, Box 2 to Grouping 2 B:
Box 2 to Grouping 2 A, Box 1 to Grouping 2 B:

You're confusing me even more. Isn't there any simpler explanation to why we don't use 3! and instead we use 3?

 

[Stephen Tashi]

You're confusing me even more. Isn't there any simpler explanation to why we don't use 3! and instead we use 3?

The usual method of showing a claim is untrue in mathematics is to give a counterexample. If you work out a detailed counter example, perhaps you can explain to yourself where your method goes wrong.

 

[andyrk]

I just got the answer on working it out with examples. Thanks :)