Answer: Number of Distributions of 5 Balls into 3 Boxes

[Punkyc7]

Find the number of distributions of 5 distinct balls into 2 red boxes and one blue box if the two red boxes are identical and no boxes are empty.

So First I assumed that the boxes were all identical and got

5!/(3!2!)+5!/(2!2!2!) =25

from there I multiplied 25 by 2 because there are 2 different color boxes which would give me 50. The solution in the book says it should be 75 but I'm not sure why that is.

 

[lanedance]

hey Punkyc7 can you explain your method a little more - how did you come to that formula?

I think this one may need a little care, maybe even to consider each case, of say B balls in blue box separately (gives 6 cases). It is a lot of cases but the formula for each should be related.

say B=0
then it becomes how to partition 5 distinct objects into 2 groups

say B=1
there are 5 choices for the ball to go into the blue box
then it becomes how to partition 4 distinct objects into 2 groups

say B=2
there are 5.4/2 choices for the 2 balls to go into the blue box
then it becomes how to partition 3 distinct objects into 2 groups

and so on, maybe not the most elegant method, but it should be understandable

 

[Punkyc7]

My book doesn't really give you any formulas, its up to you to figure it out. Most of the questions don't come with answers so its hard to known if your right or wrong.

I was thinking I would consider that the boxers were identical and I would count the partitions. From there I was thinking since 2 of the boxes are the same and 1 is different there would be twice the amount of distributions if it were to go into identical boxes.

I was thinking if all the boxes were different there would be 75. The number of distributions times 3.

 

[lanedance]

I was asking as I didn't understand what the formulas you posted in #1 represented?

Now as you mention in post #3, let's consider a case where all the boxes are different (distinct)

As the balls are distinct, let's number them 1,2,3,4,5. Then there is:
3 ways to choose the box for ball 1
3 ways to choose the box for ball 2
and so on..

so doesn't it reduce to 3^5 = 243 ways to distribute the balls in distinct boxes?

 

[lanedance]

sorry I just read the no box empty so we need to subtract the cases with:
no balls in 2 boxes
no balls in 1 box

 

[lanedance]

with post #5 on mind i have updated post #2 as below to account for the non-empty clause, which simplifies the problem

if we consider say B balls in a blue box separately, this gives 3 cases, as no box can be empty.

say B=1
there are 5 choices for the ball to go into the blue box
then it becomes how to partition 4 distinct objects into 2 groups with none empty

say B=2
there are 5.4/2 choices for the 2 balls to go into the blue box
then it becomes how to partition 3 distinct objects into 2 groups with none empty

say B=3
there are 5.4.3/(3.2) choices for the 3 balls to go into the blue box
then it becomes how to partition 2 distinct objects into 2 groups with none empty

 

[lanedance]

now considering the case where the boxes are distinct and non-empty

there are 3^5 = 243 ways to distribute the balls into any box regardless of whether they are empty. So from this we will subtract the cases that have empty boxes

accounting for the cases which have no balls in 2 boxes, there are:
- 3 ways to choose the full box

accounting for the cases which have no balls in 1 box, there are:
- 3 ways to choose the empty box
- now how to partition 5 balls into 2 distinct boxes
- as the boxes are distinct there is a total of 2^5 = 32 ways to do it
- however 2 of those will give a second empty box which we have already counted
- so there is 30 ways to partition the balls

so for the distinct box case we have a total number of distributions of
243 - 3 - (3*30) = 243 - 93 = 150

now if we consider the case where 2 red boxes are identical, the will lead to an overcount factor of 2 giving:
75

...so we got there - the method in post #6 would give a good check as well

 

[lanedance]

it may also be worth knowing about Stirling Numbers (which i only just discovered)
http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

they give the number of ways to partition n members into k non-empty subsets

 

[Punkyc7]

Thanks I think I understand it now