How many ways are there to assign $20$ different people to $3$ different rooms with at least $1$ person in each room?

Question

How many ways are there to assign $20$ different people to $3$ different rooms with at least $1$ person in each room?

I know how to approach this problem using combinations:$$17!\cdot {3 \choose 1}$$But now I want to approach this problem using inclusion-exclusion set principles, but am unsure of how to proceed.

Answer 1

One can use inclusion-exclusion in the following wordy way:

There is only one way to distribute $20$ people over $1$ room. Given $3$ rooms, there are $3\times1=3$ ways to distribute $20$ people over a single room.

There are $2^{20}$ ways to distribute $20$ people over $2$ rooms. Given $3$ rooms, there are $3$ ways to pick $2$ rooms and hence $3\times2^{20}$ ways to distribute $20$ people over two rooms, though each of the $3\times1=3$ ways to distribute $20$ people over one rooms is now counted twice. So in fact there are $$3\times2^{20}-3\times1=3\times(2^{20}-1),$$ ways to distribute $20$ people over $2$ of the $3$ rooms. Similarly, there are $3^{20}$ ways to distribute $20$ people over $3$ rooms. The count above shows that there are $3\times(2^{20}-1)$ ways to distribute $20$ people over $2$ of the $3$ rooms, so there remain $$3^{20}-3\times(2^{20}-1)=3\times(3^{19}-2^{20}+1),$$ ways to distribute $20$ people over $3$ rooms with at least $1$ person in each room.

Answer 2

The problem is that what you said you know is actually wrong. If there are only 3 people, you would get by your method a completely wrong answer, and it should be clear why it is wrong.

You need inclusion-exclusion here. How many ways to have at least 1 room empty? How many ways to have at least 2 rooms empty? If you $T$ be the collection of all possibilities, and let $S_k$ be the collection of possibilities with the $k$-th room empty, then the number of desired solutions is:

$|T| - |S_1| - |S_2| - |S_3| + |S_1 \cap S_2| + |S_1 \cap S_3| + |S_2 \cap S_3| - |S_1 \cap S_2 \cap S_3|$.

This can be simplified because by symmetry you know that:

$|S_1| = |S_2| = |S_3|$ and $|S_1 \cap S_2| = |S_1 \cap S_3| = |S_2 \cap S_3|$.

Note that each term is now easy to compute.