# Where did I go wrong in this combanitorics question?

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.

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?

• Hint: Note that you are off by a factor of 2. That should tell you something. – Asier Calbet Sep 27 '14 at 13:44
• 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. – 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.
• 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. – drhab Sep 27 '14 at 15:22