# In how many ways can people get out of the elevator?

My specific problem states that there are 8 people inside the elevator and there are 5 floors. In how many ways can they get out if there's a requirement that at least one person leaves at each floor?

The answer is 126000 and I can't get anywhere near it. I do not know if this is the correct answer.

I've tried solving the $x_1 + x_2 + x_3 + x_4 + x_5 = 3$ and then playing with the numbers but didn't get anywhere close.

I am not sure if the order by which people exit the elevator matters as nothing in the problem states that.

The numbers are small, so we can do it by cases. Maybe (Case 1) $4$ people get off at one floor, with the rest $1$ each. Or maybe (Case 2) it is $3$ on one floor, $2$ another, and the rest $1$ each. Or maybe (Case 3) it is $2$. $2$, $2$ with the rest $1$ each.

I will do Case 1, and Case 3 because it is slightly tricky. You can do Case 2.

Case 1: The floor at which the $4$ people get off can be chosen in $\binom{5}{1}$ ways. For each such choice, the actual people who get off there can be chosen in $\binom{8}{4}$ ways. Once this is done, there are $4$ floors and $4$ people. That gives $4!$ arrangements. So there are $$\binom{5}{1}\binom{8}{4}4!$$ Case 1 possibilities.

Case 3: We do this one because it is tricky, one can get the wrong answer. The special floors at which the pairs get off can be chosen in $\binom{5}{3}$ ways. Once these have been chosen, the $2$ people who get off at the lowest special floor can be chosen in $\binom{8}{2}$ ways and then the $2$ people who get off at the next special floor can be chosen in $\binom{6}{2}$ ways, and then the $2$ people who get off at the highest chosen floor can be selected in $\binom{4}{2}$ ways. Finally, the two singles can be assigned to the remaining floors in $2!$ ways. Multiply.

• I think the $\binom{5}{2}$ in your case 3 is a typo, right? (should be $\binom{5}{3}$) – gnometorule Jan 26 '13 at 2:28
• I had corrected it while editing. Luckily, it doesn't even matter, since $\binom{5}{3}=\binom{5}{2}$. – André Nicolas Jan 26 '13 at 2:30
• Good point. :). . – gnometorule Jan 26 '13 at 2:50
• @AndréNicolas In your case 3, can't we do: first floor choose in $\binom{5}{1}$, then some people get off. Second floor choose in $\binom{4}{1}$ then some people get off. And continue till last floor. Will this be an incorrect approach (and why?) Thank you! – Gaurang Tandon Dec 6 '14 at 16:03
• @GaurangTandon: As to your second question, we add. – André Nicolas Dec 6 '14 at 16:09

Looking at the equation $x_1 + x_2 + x_3 + x_4 + x_5 = 3$ only takes into account the number of people who exit onto each floor, not who the people are. What you want is to partition the set of 8 people into 5 nonempty labelled subsets. That is, you want the number of surjective functions from $\{1,\dots,8\}$ to $\{1,\dots,5\}$. See Stirling numbers of the second kind.

• I do agree that the above equation doesn't take the people as individuals but I realized that I could "paint" them but couldn't do it properly. Stirling numbers formula works for unlabeled subsets but "painting" the subsets $n \brace {k}$$\cdot 5!$ gives me the desired 126000. Thanks for the hint! – user48724 Jan 26 '13 at 2:29