# How many ways can you sit such that no two countrymen sit next to each other

In how many ways can you seat 3 Englishmen, 3 Frenchmen and 3 Turks in a row of seats, so that no two countrymen sit next to each other?

My attempt: I know this involves P.I.E (principle of inclusion and exclusion).

$$A_1$$: were English and french sit together $$A_2$$: were English and turks sit together $$A_3$$: were french and turks sit together

Total: 9! - $$(A_1 + A_2 + A_3)$$ Is this correct

• It sounds like you don't understand what it means to have two countrymen sit next to each other... You have three englishmen, lets call them $E_1,E_2,E_3$. You have three frenchmen, lets call them $F_1F_2F_3$ and you have three turks, $T_1,T_2,T_3$. An example of a good arrangement might be $E_1F_1E_2T_1F_2E_3T_2F_3T_3$. An example of a bad arrangement would be $E_1\color{red}{T_2T_3}F_1E_2T_1F_2E_3F_3$ since $T_2$ and $T_3$ are sitting together despite being from the same country. – JMoravitz Nov 25 '19 at 0:57
• Btw, answer is $37584$ if that helps. Maybe a recurrent relation will do. – Alexey Burdin Nov 25 '19 at 1:09

So we have a total of 29 ways for seating beginning AB... . There are 6 ways it could begin (AB, BA, AC, CA, BC, CB). So that gives a grand total of 174 for case (1). For case (2) we must multiply by $$6^3$$ (there are 6 ways of sitting three nationals in 3 given seats), so we get 37584.