How many ways can we put 'z' different objects into 4 boxes such thatat leasttwo boxes remain empty?

Thanks!

Printable View

- Mar 21st 2010, 08:51 AMJoAdams5000Sorting With Restrictions
How many ways can we put 'z' different objects into 4 boxes such that

**at least**two boxes remain empty?

Thanks! - Mar 21st 2010, 09:06 AMPlato
- Mar 21st 2010, 10:13 AMJoAdams5000
The four boxes in this question

**are different**.

However, I would also be interested in how the answer would change if the boxes were identical instead. - Mar 21st 2010, 10:14 AMSoroban
Hello, JoAdams5000!

I will assume that the boxes are distinguishable.

Quote:

How many ways can we put $\displaystyle z$ different objects into 4 boxes

such that*at least*two boxes remain empty?

There are only two cases:

. . (1) There are two empty boxes.

. . (2) There are three empty boxes.

Case (1): Two empty boxes

There are: .$\displaystyle {4\choose2} = 6$ choices for the 2 empty boxes.

The $\displaystyle z$ objects are partitioned between the other two boxes.

. . There are: .$\displaystyle z-1$ ways.

Hence, there are: .$\displaystyle 6(z-1)$ ways to have two empty boxes.

Case (2): Three empty boxes

There are: .$\displaystyle {4\choose3} = 4$ choices for the three empty boxes.

The $\displaystyle z$ objects are placed in the remaining box.

. . There is: .$\displaystyle 1$ way.

Hence, there are: .$\displaystyle 4\cdot1 = 4$ ways to have three empty boxes.

Therefore, there are: .$\displaystyle 6(z-1) + 4 \:=\:6z - 2$ ways to have at least two empty boxes.

- Mar 21st 2010, 10:54 AMArchie Meade
There are 4 ways to place all 21 objects into 1 of 4 boxes.

This is the number of ways to have 3 empty boxes.

For the case of 2 empty boxes, there are $\displaystyle \binom{4}{2}=4c_2=6$ ways to choose 2 of them, if they are different.

Taking one pair of 2 boxes...

the objects can be placed as follows

1 object in one box and 20 in the other

There are $\displaystyle \binom{21}{1}=21$ ways to do this as the 'z" objects are different.

2 objects in one box and 19 in the other

There are $\displaystyle \binom{21}{2}$ ways to choose 2 objects,

so that's the number of ways to place 2 in one and 19 in the other.

Continue on for 3 in one and 18 in the other, 4 in one and 17 in the other etc

and sum all the results. Multiply that sum by 6.

Add the number of ways to have 2 and 3 empty boxes.

However, there is likely to be a faster calculation. - Mar 21st 2010, 11:00 AMPlato
The objects are distinct and the boxes are distinct.

There are $\displaystyle \binom{4}{2}$ to choose two empty boxes.

There are $\displaystyle 2^z-2$ ways to assign the z objects to the two other boxes so neither is empty.

There are $\displaystyle \binom{4}{1}$ to choose three empty boxes.

There is only one way to put the objects into the remaining box.

To have either exactly two or exactly three empty boxes:

$\displaystyle \binom{4}{2}\left(2^z-2\right)+\binom{4}{3}\$.