2
$\begingroup$

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)?

$\endgroup$
2
  • 1
    $\begingroup$ The number of chairs available for D depends on where A sits. Consider the case where A sits in 2 or 4 separately from the case where he sits in 1 or 5. $\endgroup$
    – saulspatz
    Jun 21, 2018 at 19:45
  • $\begingroup$ You need to remove the permutations that don't work. There is the scenario where D sits at 1 and A at 5 and D sits at 5 and A sits at 3. $\endgroup$
    – Gregory
    Jun 21, 2018 at 19:46

2 Answers 2

3
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.