# Thread: Sorting With Restrictions

1. ## Sorting With Restrictions

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

Thanks!

2. Originally Posted by JoAdams5000
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?

3. 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.

I will assume that the boxes are distinguishable.

How many ways can we put $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: . ${4\choose2} = 6$ choices for the 2 empty boxes.

The $z$ objects are partitioned between the other two boxes.
. . There are: . $z-1$ ways.

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

Case (2): Three empty boxes

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

The $z$ objects are placed in the remaining box.
. . There is: . $1$ way.

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

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

5. Originally Posted by JoAdams5000
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 $\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 $\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 $\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.

6. Originally Posted by JoAdams5000
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.
The objects are distinct and the boxes are distinct.
There are $\binom{4}{2}$ to choose two empty boxes.
There are $2^z-2$ ways to assign the z objects to the two other boxes so neither is empty.

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