Four sets of perfectly identical twins sit in a row of 8 seats in the airport departure lounge. In how many ways can they sit so that no one is seated next to their twin?
I attempted to try this with a smaller number of sets. For example, if there were 2 sets of twins, they could be seated in 8 ways so that no one sits next to their twin.
If there are 3 sets of twins, I believe that there are 144 ways – which is 6 x 4 x 3 x 2 x 1 x 1 – for the number of options left for each seat. Unfortunately, I cannot apply this same method to 4 sets of twins. I'm not sure how to use permutations or combinatorics for this problem. I have the answer, but I could really use a hint on how to solve it.
Best Answer
Under the usual interpretation that people are distinguishable
You are correct that there are eight ways to seat two pairs of twins if neither pair of twins sits together.
As TonyK pointed out in the comments, your answer for three pairs of twins is incorrect. TonyK also provided a correct solution for that problem, but let's do it with the Inclusion-Exclusion Principle.
Number of ways three pairs of twins can be seated in a row if no pair of twins sits together
If there were no restrictions, the six people could be seated in $6!$ ways.
A pair of twins sits together: There are three ways to select the pair of twins that sits together. We have five objects to arrange, the block containing the twins that sit together and the other four people. The objects can be arranged in $5!$ ways. The pair of twins can be arranged within their block in $2!$ ways. Hence, there are $$\binom{3}{1}5!2!$$ such seating arrangements.
However, if we subtract this amount from the total, we will have subtracted too much since we will have subtracted each arrangements in which there are two pairs of twins in which the pair of twins sit together twice, once for each way we could have designated one of those pairs of twins as the pair of twins that sit together. We only want to subtract such arrangements once, so we must add them to the total.
Two pairs of twins in which the pair of twins sits together: There are $\binom{3}{2}$ ways to select the two pairs of twins in which the pair of twins sits together. We have four objects to arrange, the two blocks of twins in which the pair of twins sits together and the other two people. The four objects can be arranged in $4!$ ways. Within each block, the twins can be arranged in $2!$ ways. Hence, there are $$\binom{3}{2}4!2!2!$$ such seating arrangements.
However, if we add this amount to the total, we will have added too much since we first subtracted each arrangement in which there are three pairs of twins in which the pair of twins sits together three times, once for each of the three ways we could have designated one of those pairs as the pair of twins that sits together, and then added three times, once for each of the $\binom{3}{2}$ ways we could have designated two of those three pairs of twins as the two pairs of twins in which the pair of twins sits together. Therefore, we have not subtracted those arrangements in which there are three pairs of twins in which the pair of twins sits together, so we must subtract them from the total.
Three pairs of twins in which the pair of twins sits together: There are three objects to arrange, the three blocks containing pairs of adjacent twins. The objects can be arranged in $3!$ ways. Within each block, the twins can be arranged in $2!$ ways. Hence, there are $$\binom{3}{3}3!2!2!2!$$ such seating arrangements.
By the Inclusion-Exclusion Principle, there are $$6! - \binom{3}{1}5!2! + \binom{3}{2}4!2!2! - \binom{3}{3}3!2!2!2! = 240$$ ways to seat three pairs of twins in a row so that no pair of twins sits together.
Can you adapt this argument to solve the corresponding problem for four pairs of twins?
Under the interpretation that the "completely identical" twins are indistinguishable
Under this interpretation, there would be just two admissible arrangements of two pairs of twins: $ABAB$ and $BABA$.
Number of ways three pairs of indistinguishable twins can be seated in a row if no pair of twins sits together
This amounts to finding the number of arrangements of $AABBCC$ if no two identical letters may be adjacent.
If there were no restrictions, we could arrange the letters $A,A,B,B,C,C$ in $$\binom{6}{2}\binom{4}{2}\binom{2}{2}$$ ways since we must select two of the six positions for the $A$s, two of the remaining four positions for the $B$s, and both of the remaining two positions for the $C$s.
A pair of identical letters is adjacent: There are three ways to select the pair of identical letters that are adjacent. We have five objects to arrange, the double letter and the other four letters. For instance, suppose the objects are AA, B, B, C, C. We can arrange the five objects in $$\binom{5}{2}\binom{3}{2}$$ ways since we must select two of the five positions for the $B$s, two of the remaining three positions for the $C$s, and then fill the final position with the $AA$. Hence, there are $$\binom{3}{1}\binom{5}{2}\binom{3}{2}$$ such arrangements.
Two pairs in which a pair of identical letters are adjacent: There are $\binom{3}{2}$ ways to select the two pairs in which a pair of identical letters is adjacent. Then we have four objects to arrange, the two pairs of adjacent identical letters and the other two letters. Suppose the objects are $AA, BB, C, C$. The objects can be arranged in $$\binom{4}{2}2!$$ ways since we must select two positions for the $C$s, then we can arrange the two distinct double letters in the remaining two positions in $2!$ ways. Hence, there are $$\binom{3}{2}\binom{4}{2}2!$$ such arrangements.
Three pairs in which a pair of identical letters is adjacent: We have three objects to arrange: $AA, BB, CC$. Since they are distinct, they can be arranged in $3!$ ways.
Hence, by the Inclusion-Exclusion Principle, the number of arrangements of three pairs of "completely identical" twins in which no pair of twins sits together is $$\binom{6}{2}\binom{4}{2}\binom{2}{2} - \binom{3}{1}\binom{5}{2}\binom{3}{2}1! + \binom{3}{2}\binom{4}{2}2! - \binom{3}{3}3! = 30$$
Can you adapt this argument to four pairs of "completely identical" twins?