Eight people enter an elevator. At each of the four floors at least one person leaves the elevator after which elevator is empty. The number of ways in which this is possible, is

(A) $$\sum_{i=0}^4 \binom 4i (-1)^{i}(4-i)^{8}$$

(B) $$\sum_{i=0}^4 \binom 8i (-1)^i(8-i)^4$$

(C) Less than $4^8$

(D) $\binom 84 -1$

I tried this by listing all the cases $$ \begin{matrix} 5&1&1&1\\ 4&2&1&1\\ 3&2&2&1\\ 3&3&1&1\\ 2&2&2&2\\ \end{matrix} $$ Since question does not asks for exact number I believe there might be other way to solve this.

Division into groups can possible. Arranging 8 persons into 4 groups with each group having one or more than one person

Please provide complete explanation as combinatorics is not easy for me.

p.s More than one options can be correct.


If conditions are left out then there are $4^8$ possibilities.

For $i=1,2,3,4$ let $A_i$ denote the collection of possibilities under the condition that no person leaves the elevator at floor $i$.

Then you are looking for: $$|A_1^c\cap A_2^c\cap A_3^c\cap A_4^c|=4^8-|A_1\cup A_2\cup A_3\cup A_4|$$

We can find $|A_1\cup A_2\cup A_3\cup A_4|$ by means of inclusion/exclusion and symmetry.

Actually: $$|A_1\cup A_2\cup A_3\cup A_4|=4|A_1|-6|A_1\cap A_2|+4|A_1\cap A_2\cap A_3|=4\times3^8-6\times2^8+4$$ So the number of solutions is:$$4^8-4\times3^8+6\times2^8-4$$ This agrees with answer (A).

If you are only looking at the number of persons leaving at each floor (so not the persons themselves) then you must find the number of sums $$f_1+f_2+f_3+f_4=8$$ where the $f_i$ are positive integers.

It is the same as finding the number of sums $$e_1+e_2+e_3+e_4=4$$ where the $e_i=f_i-1$ are non-negative integers.

That can be solved with stars and bars, and leads to: $$\binom{4+3}3=\binom73$$ solutions.


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.