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

combinatorics

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

Best Answer

There are two cases, (1) where we disregard everything about a person except their nationality, and (2) where we don't. Start with (1).

Label the nationalities A,B,C. Suppose the first two seats are AB. Then the third seat can be A or C. Suppose it is A. It is not hard to see that there are just 9 possibilities:

ABAB followed by CACBC or CBCAC; ABACA followed by BCBC or CBCB; ABACBACBC; or ABACBC followed by ABC, ACB, BAC or BCA.

If the third seat is C, then we have ABCAB, ABCAC, ABCBA or ABCBC. Each of these will give the same number of possibilities because each has used up two instances each of two letters and one of the third.

ABCABA must be followed by CBC. ABCABC must be followed by one of ABC, ACB, BAC, BCA. That is 5 ways. So 4 x 5 = 20 in all for ABC...

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.