How many ways can we put 'z' different objects into 4 boxes such that at least two boxes remain empty?
Thanks!
Hello, JoAdams5000!
I will assume that the boxes are distinguishable.
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.
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.
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}\$.