How to distribute 15 distinct objects into 5 distinct boxes with at least 3 boxes empty?

Question

How to distribute 15 distinct objects into 5 distinct boxes with at least 3 boxes empty

Can someone help solve this? Is there a common formula I can use to find ways to distribute n distinct objects into K distinct boxes with at least x boxes empty

Answer 1

The main tool is:

$n$ distinct objects can be placed in $k$ distinct boxes in $k^n$ ways: for each of the $n$ objects, we can add it to one of the $k$ boxes.

Let's label the boxes $1,2,3,4,5$. If you're able to answer these questions, then the rest is arithmetic:

• How many subsets of size $4$ are there in $\{1,2,3,4,5\}$?
• Given any subset $S \subseteq \{1,2,3,4,5\}$ of size $4$, how many arrangements are there in which the boxes in $S$ are empty, and the boxes outside of $S$ are not empty?
• How many subsets of size $3$ are there in $\{1,2,3,4,5\}$?
• Given any subset $S \subseteq \{1,2,3,4,5\}$ of size $3$, how many arrangements are there in which the boxes in $S$ are empty, and the boxes outside of $S$ are not empty?

The last question above is the tricky part. For example, if the boxes are labelled $\{1,2,3,4,5\}$, and we insist on the boxes $\{3,4,5\}$ being empty, then there are $2^{15}$ arrangements (using the "main tool" above), but we also need to exclude the cases that box $1$ or box $2$ is also empty (but not both---we can't have all 5 boxes empty).