# 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