Principle of Inclusion-Exclusion Problem

Question

The setup: I bought 8 distinguishable beds for my 3 (distinguishable) bedroom apartment. I want to put at least one bed in each of my bedrooms, and all beds must be placed in a bedroom. How many ways can I place my beds in my bedrooms? The question hinted at using the Principle of Inclusion-Exclusion in my answer.

I'm honestly really stuck at how I can approach this problem.

Answer 1

I think a picture would help you a lot.

Lets say an arrangement is valid if no bedroom is empty. To get the number of valid ways, we take all the possible ways of arranging the beds ($3^8$) and subtract the invalid ways. The invalid ways can be shown in the picture as the sum of all three circles. So by PIE, we want to calculate $$ \text{sum of all 3 circles} - \text{ sum of intersection of all pairs of circles } + \text{ sum of intersection of all 3 circles }$$

Now, lets compute the size of each type of area. Each circle has size $2^8$. The intersection of any two pairs of circle has size $1^8$. The intersection of all 3 circles has size $0$ (the beds have to go somewhere!). Hence, we get

$$ \text{no. of invalid ways} = (2^8 + 2^8 + 2^8) - (1^8 + 1^8 + 1^8) + 0$$