Six People Permutation in Linear Arrangement With Exceptions

Question

I can't seem to wrap my head around this. My professor hasn't done anything like this in class, and all I've found on the internet on this are circular arrangements.

We have Arnie, Betty, Carl, Debbie, Ernie, and Felicia

Ernie and Felicia refuse to be seated by each other AND Arnie and Betty refuse to be seated beside each other. How many line-ups are possible?

Answer 1

The idea would be to use the principle of inclusion and exclusion. Count all permutations ($6!=720$), then count ($=X$) all the permutations where E and F sit next to each other, count ($=Y$) all the permutations where A and B sit next to each other, finally count ($=Z$) all the permutations where A and B sit next to each other and E and F also sit next to each other.

The number you are looking for is then

$$720 - X - Y + Z$$

To calculate $X$, there are 5 ways to choose the neighbouring seats for E and F $((1,2), (2,3),\ldots,(5,6))$, 2 ways to seat E and F there, and finally $4!=24$ to seat the remaining four people in the remaining four seats. So we get

$$ X=5 \times 2 \times 24 = 240$$.

The calculation for $Y$ is exactly the same, as it is exactly the same problem, so we get $Y=240$.

To calulate $Z$, we need to determine which pairs of neighbouring seats are compatible for the (E/F) and (A/B) pairs. That's because if (E/F) sit in the seats $(1,2)$, then (A/B) can't sit in $(2,3)$.

So we get (while listing the earlier pair first) the following list of compatible pairs:

• $(1,2)$: $((3,4), (4,5), (5,6))$
• $(2,3)$: $((4,5), (5,6))$
• $(3,4)$: $((5,6))$

This means there are $3+2+1=6$ pairs of 'compatible' neighbouring seats to take for (E/F) and (A/B).

We can assign the 2 pairs of seats to the 2 pairs of people in 2 ways. Once (E/F) has their pair of seats, they can sit there in 2 ways. The same goes for (A/B). The remaining 2 people (C and D) can also take the remaining 2 seats in 2 ways.

So we get

$$ Z= 6 \times 2 \times 2 \times 2 \times 2 = 96$$ (corrected due to comment)

So the number you are looking for, the number of permutations where neither E and F nor A and B sit next to each other is

$$ 720 - 240 - 240 + 96 = 336$$

Answer 2

Okay this is wrong. Leaving it up for the comments.

There are 2 times (6 choose 2) = 30 ways to pick where Ernie and Felicia sit.

Then 2 times (4 choose 2) =12 ways to choose where Arnie and Betty sit.

Then just 2 ways to seat the remaining Carl, Debbie

Multiply these together to get 720