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

  • 1
    $\begingroup$ 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. $\endgroup$ – JMoravitz Nov 25 '19 at 0:57
  • $\begingroup$ Btw, answer is $37584$ if that helps. Maybe a recurrent relation will do. $\endgroup$ – Alexey Burdin Nov 25 '19 at 1:09

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.