1
$\begingroup$

We have to seat 10 people in a row.

Condition: two people always sit together and two people never sit together.

My attempt: Let the two people who always sit together be taken as 1 person for the time being. So, we have nine people.

1) Keep one of two people who never sit together at seat 1. Then, we have $7\cdot8!$ ways to seat others.

2) Keep that person at seat 2. Then, we have $6\cdot8!$ ways to seat others.

3) Adding up the above iterations, we have $8!(7\cdot2+6\cdot7)$ ways.

4) Finally the two pairs can be permutated in 2 ways each.

Hence, the answer should be $4\cdot8!(7\cdot2+6\cdot7)$.

Is this correct?

Is there a better approach to solve this problem ? Please advise.

$\endgroup$
4
$\begingroup$

The way I would solve this is taking the number of ways of seating the ten people without the condition that the two don't sit together ($2 \cdot 9!$) and subtracting the number of configurations where they sit together ($2^2 \cdot 8!$). So the answer is $2 \cdot 9! - 2^2 \cdot 8! = 564480$.

Your method would also work, but you have made two mistakes. Firstly your $8!$'s should be $7!$, we are seating nine people in total and the two who don't sit together have already been seated, so there are seven people left. Secondly, you should not multiply the final answer by $2$ for the people who don't sit together, you have already counted both ways for them to sit. So the correct answer is $2 \cdot 7!(7 \cdot 2 + 6 \cdot 7) = 564480$.

$\endgroup$
  • $\begingroup$ your way makes it easier to solve similar problems .. Thanks :) $\endgroup$ – square_one Jan 17 '15 at 8:19
  • $\begingroup$ @Arthur, how did you come up with $2^2 \cdot 8!$ ? $\endgroup$ – Mark Lao Jan 17 '15 at 8:44
  • 1
    $\begingroup$ View each of the pairs as being just one person. Then there are $8!$ ways to permute the eight "people" and finally $2$ ways to permute each of the pairs. $\endgroup$ – Arthur Jan 17 '15 at 9:02
2
$\begingroup$

There are some issues with your solution - I'm not sure exactly where some of the numbers came from in "$8!(7\cdot2+6\cdot7)$", for example.

As you say, we can treat the two people sitting together as one person (with $2$ permutations), and temporarily consider nine seats. For the people sitting apart, denote them with A and all others with B.

Consider the order of the the seven Bs has been chosen, $7!$ options, and imagine there are gaps in between their seating positions and at the ends. The two As have to be inserted into two of those 8 gaps, $8 \times 7$ options.

Total choices, then: $ 2\times 7! \times 8\times 7 = 14 \times 8! =564480$

$\endgroup$
1
$\begingroup$

It's also worth noting that your answer exceeds 10!, which is the number of seating arrangements without any restrictions.

I suggest that you do this quick test as an initial checking for the correctness of your answer.

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