The question is as follows:

A fancy bed and breakfast inn has $5$ rooms, each with a distinctive color-coded decor. One day $5$ friends arrive to spend the night. There are no other guests that night. The friends can room in any combination they wish, but with no more than $2$ friends per room. In how many ways can the innkeeper assign the guests to the rooms?

There are $3$ cases that we have to consider:

  • All $5$ people stay in their own room
  • $3$ people stay in their own rooms, $2$ people stay in one room
  • $1$ person stays in his own room, $2$ rooms with $2$ people in it

So I calculated correctly for the first two cases (which are $120$ and $1200$ respectively). For the last case however, I get $1800$ but the solutions states it's $900$.

My Try:

$5$ choices for the first room with two people, then you have to choose the two people that go into it, for a total of $5*{5 \choose 2}$ ways. Then you choose two more people to stay in a room together, and they have a choice of 4 rooms to stay in, for a total of $4*{3 \choose 2}$ ways, then the lonely person has 3 rooms to choose from, forming a total of $5*{5 \choose 2}*4*{3 \choose 2}*3 = 1800$ ways.

The Answer Key:

Two rooms house two guests; one houses one. We have $\binom{5}{2}$ to choose the two rooms with two people, and $\binom{3}{1}$ to choose one remaining room for one person. Then there are 5 choices for the lonely person, and $\binom{4}{2}$ for the two in the first two-person room. The last two will stay in the other two-room, so there are $\binom{5}{2}\binom{3}{1}\cdot5\cdot\binom{4}{2}=900$ ways.

The answer key makes sense, but what did I do wrong to overcount?

  • 2
    $\begingroup$ Hint: Note that you are off by a factor of 2. That should tell you something. $\endgroup$ – Asier Calbet Sep 27 '14 at 13:44
  • $\begingroup$ The answer you accepted essentially explains how you doubled counted and so had to divide by two, accounting for the factor of two I was talking about. That is why I meant it as a hint. So, jeez, thanks for your sarcasm. $\endgroup$ – Asier Calbet Sep 27 '14 at 21:57

Suppose you first choose persons $A$ and $B$ and then you choose room $1$ for them.

Secondly you choose persons $C$ and $D$ and then you choose room $2$ for them.

Now another choice: first the persons $C$ and $D$ and for them room $2$ is chosen, then the persons $A$ and $B$ and for them room $1$ is chosen.

Another choice but the same outcome. This explains your double-counting.

  • $\begingroup$ Thanks this makes sense. How do I avoid this? What approach do I take? $\endgroup$ – Vishwa Iyer Sep 27 '14 at 14:30
  • $\begingroup$ If $5$ persons are split up in groups of e.g. $2$ and $3$ then the groups are distinguishable by their cardinality ($2\neq 3$). There are $\frac{5!}{2!3!}=10$ possibilities. This is different if they are split up in $2$, $2$ and $1$. There are two groups of $2$ that are not distinguishable. You must compensate that by dividing with $2!$. There are not $\frac{5!}{2!2!1!}=30$ possibilities, but there are $\frac{30}{2!}=15$ possibilities. $\endgroup$ – drhab Sep 27 '14 at 15:22
  • $\begingroup$ Ah ok that makes sense. Thank you $\endgroup$ – Vishwa Iyer Sep 27 '14 at 16:15

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.