There are 4 distinct rooms and 8 (distinct) students. Each student must occupy a room and no room is empty. How many arrangement is possible?
My attempt
-
First fill each room with one student to make sure there is no empty room. There are $P(8,4)=\frac{8!}{4!}$ ways. There are 4 students left for the next steps.
-
For the remaining 4 students, there are $4^4$ ways.
-
The total is $\frac{8!}{4!}\times 4^4 = 430 080$ ways which is not the same as the key of 40824.
Could you tell me how to solve this problem? As it is for high school students, I don't think we need generating function, right?
Best Answer
Your approach is incorrect since filling each room first and then filling the rooms with the remaining students over counts since each distribution in which more than one student is assigned to a room is counted multiple times, once for each way of designating one of the students in the room as the student who is assigned to that room.
If there were no restrictions, we would have four choices for each of the eight students, so there are $4^8$ possible distributions of students to rooms. From these, we must subtract those distributions which leave one or more rooms empty.
There are $\binom{4}{k}$ ways to leave exactly $k$ of the rooms empty and $(4 - k)^8$ ways to distribute the eight students to the remaining $4 - k$ rooms. By the Inclusion-Exclusion Principle, the number of ways eight students can be distributed to four rooms so that no room is left empty is $$\sum_{k = 0}^{4} (-1)^k\binom{4}{k}(4 - k)^8 = 4^8 - \binom{4}{1}3^8 + \binom{4}{2}2^8 - \binom{4}{3}1^8 + \binom{4}{4}0^8$$