How to apply principle of inclusion-exclusion to this problem?

Eight people enter an elevator at the first floor. The elevator discharges passengers on each successive floor until it empties on the fifth floor. How many different ways can this happen

The people are distinguishable.

  • $\begingroup$ What have you tried? Are the persons distinguishable, or are only the numbers of persons relevant? Add this to your question (not in a comment). $\endgroup$ – drhab Jun 22 '15 at 8:58

We have $4^8$ possibilities to do it with out any restrictions. We want to count the bad cases, that is cases where there is a floor which no one get down in. Here you must use inclusion-exclusion.

$A_i=$ number of ways in which no one drops in the $i$ floor.

You need to calculate the cardinality of $X$ where $$X=A_2\cup \cup A_3 \cup A_4 \cup A_5,$$ and your answer is $$4^8-|X|.$$

  • $\begingroup$ So we assume that atleast one person is unloaded on each floor? $\endgroup$ – Pradeep Jun 22 '15 at 9:25
  • $\begingroup$ @Pradeep , Yes because "discharges passengers on each successive floor". $\endgroup$ – Ofir Schnabel Jun 22 '15 at 9:26

Hint: There are $ \sum_{j=0}^k (-1)^{k-j}{{k}\choose {j} }j^n$ ways. k are the number of distinguishable people and n is the number of floors.

The formula can be looked up under the term "twelvefold way" and "Sterling number" (second kind).

  • $\begingroup$ Tried the same formula. But did not get the right answer. The correct answer is $4^8 - \binom{4}{1} 3^8 + \binom{4}{2} 2^8 - \binom{4}{3} 1^8$ $\endgroup$ – Pradeep Jun 22 '15 at 9:09
  • 1
    $\begingroup$ @Pradeep Your answer is "correct" for distinguishable passengers, assuming that at least one passenger gets off at each floor. A translation error, perhaps? $\endgroup$ – bof Jun 22 '15 at 9:17
  • $\begingroup$ @Pradeep I have made an edit. $\endgroup$ – callculus Jun 22 '15 at 9:33

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.