0
$\begingroup$

This question already has an answer here:

A hostel has four vacant rooms. Each room can accommodate a maximum of four people. In how many different ways can six people be accommodated in four rooms.

The answer is 4020.

My case by case analysis leads to a number in the 7000s:

Listing the rooms as so

4 2 0 0

4 1 0 0

3 3 0 0

3 2 1 0

3 1 1 1

2 2 2 0

2 2 1 1

Now for each of the above case I went (e.g for first case) 6C4 * 2C2 * 0C0 * 0C0 * 4!

$\endgroup$

marked as duplicate by Lord Shark the Unknown, Claude Leibovici, Guy Fsone, hardmath, Stefan4024 Dec 25 '17 at 21:25

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ It would seem your question is: "Why does my case-by-case analysis give the wrong answer?" But it's pretty hard for us to answer that when you don't explain your case-by-case reasoning. $\endgroup$ – Semiclassical Oct 14 '14 at 23:55
7
$\begingroup$

Your calculations for the individual cases aren’t right. For the first case, for instance, there are $\binom64$ ways to choose the $4$ who share a room, and there are $4$ ways to choose their room; the other $2$ will share a room, and there are $3$ ways to choose their room, for a total of $\binom64\cdot4\cdot3=180$ possibilities.

The problem can certainly be solved that way, but there’s a much more efficient way. If the rooms were large enough to accommodate all $6$ people, there would be $4^6$ possible arrangements. However, $4$ of those arrangements have all $6$ in one room, and some have $5$ in one room and $1$ in another; all of those must be subtracted from $4^6=4096$. I leave it to you to count the $\langle5,1,0,0\rangle$ arrangements; the calculation is very much like the one for $\langle 4,2,0,0\rangle$ that I gave above.

$\endgroup$
  • $\begingroup$ Ah I see. So in other words I was counting repetitions of empty rooms. Can you explain why the total combinations would be 4^6? $\endgroup$ – Orange Peel Oct 15 '14 at 0:17
  • 1
    $\begingroup$ @OrangePeel because each person can chose one of the 4 rooms. So their are 4 choices possible for person A * 4 for person B * ...; 4 * 4 * 4 * 4 * 4 * 4 = 4^6 possible choices. $\endgroup$ – Aegis Oct 15 '14 at 0:19
  • 1
    $\begingroup$ There are 4 possible rooms for each of the 6 persons, for a total of $4^6$ possibilities. $\endgroup$ – Derek Oct 15 '14 at 0:19

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