Numer of possibilities of placing people of different nationalities

Question

How many ways of sitting 3 people of nationality A, 3 of nationality B and 3 of nationality C there are if no two people of the same nationality can sit near each other (so such placings are prohibited: AABACBCBC, BCCAABCAB)

I came to such result: $\frac{9!}{(3!)^3}- {3 \choose 1} {3 \choose 2}\frac{8!}{(3!)^3} + {3 \choose 2} \frac{7!}{(3!)^3} - {3 \choose 3}{3 \choose 2} \frac{6!}{(3!)^3}$ Which is most likely bad - can anyone help me get the correct answer?

Answer 1

There are 8 spaces between seats. Let $a$ be the total number of these spaces where people of nationality A are found of both sides, and $b$ for nationality B, and $c$ for nationality C. Clearly $0\leqslant a, b, c \leqslant 2$.

Let $$N_{\alpha,\beta,\gamma} = N\left(a\geqslant \alpha,b \geqslant \beta,c \geqslant \gamma\right)$$ the number of sitting configurations with $a$, $b$, $c$ exceeding given values.

By the inclusion exclusion principle we are after $$ \sum_{\alpha=0}^2 \sum_{\beta=0}^2\sum_{\gamma=0}^2 (-1)^{\alpha+\beta+\gamma} N_{\alpha,\beta,\gamma} $$

To compute $N_{\alpha,\beta,\gamma}$ we replace each block of people of the same nationality with a person of a new nationality and use the multinomial coefficient to count configurations:

In[28]:= Sum[(-1)^(a + b + c) Multinomial[Sign[a], Max[0, 3 - (2 a)], 
   Sign[b], Max[0, 3 - 2 b], Sign[c], Max[3 - 2 c, 0]], {a, 0, 2}, {b,
   0, 2}, {c, 0, 2}]

Out[28]= 174

Confirmation with the direct counting in Mathematica:

In[31]:= Length[
 DeleteCases[
  Permutations[{a, a, a, b, b, b, c, c, c}], {___, n_, n_, ___}, {1}]]

Out[31]= 174

Answer 2

This may not be a good way to solve it, but this will give the answer.

We have $$\frac{6!}{3!3!}$$ patterns to arrange three $A$s and three $B$s.

1) In each of $BBBAAA,AAABBB,BAAABB$ case, since there are four places where two same letters are next to each other, we can't arrange $C$s in them.

2) In each of $ABBBAA, AABBBA,BBAAAB$ cases, we have to arrange three $C$s as $$ABCBCBACA, ACABCBCBA,BCBACACAB$$ So, each case has $1$ way to arrange $C$s.

3) In each of $BBABAA,BBAABA,BABBAA$, $BAABBA,ABBAAB,ABAABB,AABABB,AABBAB$ cases, we have to arrange two $C$s as $$BCBABACA, BCBACABA,BABCBACA,BACABCBA,$$$$ABCBACAB,ABACABCB,ACABABCB,ACABCBAB$$ So, each case has $\binom{5}{1}=5$ ways to arrange the last $C$.

4) In each of $BABABA,ABABAB$, we have $\binom{7}{3}=35$ ways to arrage three $C$s.

5) In each of $BABAAB,BAABAB,ABBABA,ABABBA$, we have to arrange one $C$ as $$BABACAB,BACABAB, ABCBABA, ABABCBA.$$ So, each case has $\binom{6}{2}=15$ ways to arrange two $C$s.

Thus, the number we want is $$3\times 1+8\times 5+2\times 35+4\times 15=173.$$