# Sorting With Restrictions

• Mar 21st 2010, 08:51 AM
Sorting 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 AM
Plato
Quote:

How many ways can we put 'z' different objects into 4 boxes such that at least two boxes remain empty?

Are the boxes labeled or unlabeled? That is are the boxes identical or not?
• Mar 21st 2010, 10:13 AM
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 AM
Soroban

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 AM
Quote:

How many ways can we put 'z' different objects into 4 boxes such that at least two boxes remain empty?

Thanks!

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 AM
Plato
Quote:

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.
$\displaystyle \binom{4}{2}\left(2^z-2\right)+\binom{4}{3}\$.