There are $3$ different rooms and $6$ people. How many different ways are there to put the $6$ people into the $3$ rooms if each room has to have at least $1$ person?

I am not sure I am right. I figure there are $2^6-2 = 62$ different ways to put $6$ people into $2$ rooms without having either of the $2$ rooms being empty, and there are 3 different ways to put all 3 people into a single room, so for the answer I got $3^6-3(62)-3=540$. Is this right? Is there another way to do this more directly?

  • 1
    $\begingroup$ if you are counting only the number of people then refer to this theorem #1 $\endgroup$ – Santosh Linkha Jan 1 '14 at 6:26
  • $\begingroup$ To get the $3^6 = 729$ total ways to put 6 people into 3 different rooms, I used this. I think that part is fairly straightforward. $\endgroup$ – Carter Jan 1 '14 at 6:33
  • $\begingroup$ Are you taking into consideration that people are distinct or just counting number of people?? $\endgroup$ – Santosh Linkha Jan 1 '14 at 6:37
  • 1
    $\begingroup$ The working is right (you might want to check your calculation. The final answer should be 540 instead of 602). The other way is to go by cases, boiling down to (1,1,4), (1,2,3), (2,2,2). Ordering them the right way gives the same answer of 540. $\endgroup$ – Kelvin Soh Jan 1 '14 at 6:37

As you noticed, for 2 rooms the excluded cases are only when 1 room is used, but for 3 rooms the excluded cases include when 2 rooms are used, which is why you had to reuse the answer from the case of 2 rooms. When encountering this kind of situation in general, you should try the inclusion-exclusion principle. For this you get $\binom{3}{3}3^6 - \binom{3}{2}2^6 + \binom{3}{1}1^6 - \binom{3}{0}0^6 = 3^6 - 3 \cdot 2^6 + 3$ which is the same as your answer.

  • $\begingroup$ As Kelvin pointed out, your final expression is correct but the answer is 540, not 602. I didn't notice that! $\endgroup$ – user21820 Jan 1 '14 at 6:39
  • $\begingroup$ OK, thanks a ton. I was a little confused, because I did it another way by doing $\binom{6}{3}(3^3)$ and got 540, so everything makes sense now. Sorry - that was a dumb mistake on my part. $\endgroup$ – Carter Jan 1 '14 at 6:43
  • $\begingroup$ Wait where did you get $\binom{6}{3}3^3$ from? $\endgroup$ – user21820 Jan 1 '14 at 6:45
  • $\begingroup$ I figured that you could choose any 3 people from the 6 people, one for each room, and then the other 3 people could go to any other room. thus $\binom{6}{3}(3^3)$. Is that right? $\endgroup$ – Carter Jan 1 '14 at 6:50
  • $\begingroup$ No that's not right. For example, I can have 1 room, then your method will give at least $\binom{6}{1}$, but there is only 1 solution. $\endgroup$ – user21820 Jan 1 '14 at 6:51

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.