Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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

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.

share|improve this answer
1  
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! –  Looft Jan 26 '13 at 2:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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