5 persons and 5 chairs

Question

There are 5 persons: A, B, C, D and E. There are also five chairs: 1, 2, 3,4 and 5. How many ways there are to organize these five persons on these five chairs, given that the person A can't sit on chair 3 and that the person D can't sit on chairs 1 and 5?

---

My attempt

Well, there are $5!=120$ ways to organize persons if all of them could sit on every chair. Now, let's see how many permutations there are in the case that the person A sits on chair 3: $4\cdot3\cdot1\cdot2\cdot1=24$. And in the case that the person D sits on chair 1: $1\cdot2\cdot3\cdot4\cdot1$. And if person D sits on chair 5: $4 \cdot 3 \cdot 2 \cdot 1 \cdot 1=24$.

Therefore $$120-3\cdot24=120-48=52$$ But that isn't correct! The correct answer is $60$. Why is my answer wrong and what is the correct way to solve this problem (I'm suspecting that my answer is wrong because I include person A on chair 3)?

Answer 1

Let's start with person D who is the most restrictive. We will consider 2 cases:

D sits in chair 2 or 4

D sits in chair 3

If D sits in chair 2 or 4, next, we look at person A who cannot sit in chair 3. There are only 3 chairs available to A. Then 3 to B, 2 to C, and 1 to E. That is: $2\cdot 3\cdot 3\cdot 2\cdot 1 = 36$

If D sits in chair 3, then there are $4!=24$ ways to arrange the remaining people, as there are no more restrictions.

That's a total of 36+24=60.

---

Now, let's try with your method (we take the total number of permutations and subtract restricted cases).

As you found, there are 120 total permutations. There are $2\cdot 4\cdot 3\cdot 2\cdot 1=48$ permutations where D is in either chair 1 or 5. There are $1\cdot 4\cdot 3\cdot 2\cdot 1 = 24$ permutations where A is in chair 3.

The number of permutations with A in chair 3 OR D in chair 1 or 5 equals the number of permutations of A in chair 3 plus the number of permutations of D in chair 1 or 5 minus the permutations of both. So, there are $2\cdot 1\cdot 3\cdot 2\cdot 1 = 12$ permutations where both occur.

$120-(48+24-12) = 60$.

Answer 2

You have removed twice the cases where A sits in 3 and D sits in 1 or 5. You need to add them back in once. This is the inclusion-exclusion principle. Alternately you can remove all the cases where A sits in 3, then remove the ones where D sits in 1 or 5 but A doesn't sit in 3.