1
$\begingroup$

Eight people enter an elevator. At each of four floors at least one person leaves the elevator after which the elevator is empty. What is the number of ways in which this is possible? I tried to do it by using the following method:

At the first floor for example, a minimum of $1$ and a maximum of $5$ people can leave the elevator. So this can be done in $ \binom{8}{1} + \binom{8}{2} + \binom{8}{3} + \binom{8}{4} + \binom{8}{5}$ ways. Now if we suppose that only one person leaves the elevator on the first floor we are left with $7$ people of which a minimum of $1$ and a maximum of $5$ can leave at the second floor. Again we’d have to generalize for the third floor and so on. Also, here we are considering the case in which only one person leaves the elevator on the first floor. There would be many such cases and sub cases for $2$ , $3$, etc. people leaving the elevator at the first floor. How can I generalize all of these cases?

$\endgroup$
  • $\begingroup$ @Skyhit2 Generalize is the American English spelling; generalise is the British English spelling. $\endgroup$ – N. F. Taussig Nov 19 '17 at 12:57
1
$\begingroup$

Each person has four choices where to depart the elevator. Therefore, if there were no restrictions, there would be $4^8$ ways for the eight people to depart the elevator. From these, we must exclude those choices in which no people leave the elevator on a particular floor.

There are $\binom{4}{k}$ ways to exclude $k$ of the four floors as possible exits and $(4 - k)^8$ ways for people to exit the elevator on the remaining $4 - k$ floors. Therefore, by the Inclusion-Exclusion Principle, the number of ways the people can depart the elevator so that at least one person departs on each floor is $$\sum_{k = 0}^{4} (-1)^k\binom{4}{k}(4 - k)^8 = \binom{4}{0}4^8 - \binom{4}{1}3^8 + \binom{4}{2}2^8 - \binom{4}{3}1^8 + \binom{4}{4}0^8$$

$\endgroup$
  • 1
    $\begingroup$ Okay thank you very much. $\endgroup$ – Aditi Nov 19 '17 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.