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.
Best Answer
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.