Numer of possibilities of placing people of different nationalities 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?
 A: 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

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