# Number of permutations of $9$ people of three nationalities in which no two people of the same nationality are adjacent

$9$ different people must be put in a row.

Three of them are of nationality $X$, three are of $Y$, and the remaining three are of $Z$.

In how many combinations there will be no two people of the same nationality sitting next to each other?

My understanding:

I couldn't find a pattern to follow if few are already occupied. Like, if the first seat is occupied by a person of nationality $X$ then the next seat can be occupied by $6$ other people from $Y$ or $Z$, and then the tree grows where I can't seem to have a control on.

Any hints will be appreciated.

• Are you familiar with the Inclusion-Exclusion Principle? Sep 13, 2017 at 6:34
• @N.F.Taussig Will look at it. Until then, could you give some hints as an answer? Sep 13, 2017 at 6:40
• @N.F.Taussig I looked it up. Although I couldn't formulate the problem which fits the Inclusion-Exclusion Principle. Any hints for formulating it? Sep 13, 2017 at 7:11
• @N.F.Taussig After a little struggle I got this: 9!-(3(7!*3!) - 3(5!*(3!)^2) + (3!)^4). Is this right? The first term is total possibilities, second term is one nationality group being together, third term is two nationality groups being together, and the fourth being all nationality people being together to each other. Sep 13, 2017 at 7:24

If you are not familiar with the Inclusion-Exclusion Principle, observe that there are $\binom{6}{3}$ ways to arrange three $X$s and three $Y$s (ignoring permutations of the individuals within a country for now). Consider those that begin with $X$.

$\color{red}{XXXYYY}$

$\color{blue}{XXYXYY}$

$\color{blue}{XXYYXY}$

$\color{green}{XXYYYX}$

$\color{blue}{XYXXYY}$

$XYXYXY$

$\color{brown}{XYXYYX}$

$\color{blue}{XYYXXY}$

$\color{brown}{XYYXYX}$

$\color{green}{XYYYXX}$

It is not possible to insert three $Z$s in the arrangement $\color{red}{XXXYYY}$ to separate the $X$s and $Y$s.

In the arrangements $\color{green}{XXYYYX}$ and $\color{green}{XYYYXX}$, there is only one way to insert the $Z$s to separate the $X$s and $Y$s since a $Z$ must be inserted wherever two consecutive identical letters appear.

In the arrangements $\color{blue}{XXYXYY, XXYYXY, XYXXYY, XYYXXY}$, two $Z$s must be used to separate consecutive identical letters. Once this is done, we are left with five places to insert the remaining $Z$. For instance, with the arrangement $\color{blue}{XZXYXYZY}$, the remaining $Z$ can be inserted in one of the spaces indicated by a square.

$\color{blue}{\square XZX \square Y \square X \square YZY \square}$

In the arrangements $\color{brown}{XYXYYX}$ and $\color{brown}{XYYXYX}$, one $Z$ must be inserted in order to separate consecutive identical letters. To ensure that identical letters are separated, we must choose two of the six spaces adjacent to $X$ or $Y$ but not $Z$ in which to insert the remaining $Z$s. For instance, in the arrangement of $XYXYZYX$, we must choose two of he spaces indicated by a square in which to insert the remaining $Z$s.

$\color{brown}{\square X \square Y \square X \square YZY\square X\square}$

In the arrangement $XYXYXY$, we must choose three of the seven spaces indicated by a square in which to insert the $Z$s.

$\square X \square Y \square X \square Y \square X \square Y \square$

By symmetry, there are an equal number of permissible arrangements in those permutations created by interchanging the roles of $X$ and $Y$.

Finally, observe that within each of these arrangements, people of the same nationality can be permuted in $3!$ ways, so we must multiply the number of permissible arrangements of three $X$s, three $Y$s, and three $Z$s by $(3!)^3$.

• It's not clear how this relates to the inclusion-exclusion principle. Sep 13, 2017 at 7:44
• @skyking I thought the OP was unfamiliar with the Inclusion-Exclusion Principle, so I wrote an answer that does not use the Inclusion-Exclusion Principle. I am now writing an answer based on the Inclusion-Exclusion Principle. Sep 13, 2017 at 7:45
• Great. So, the final answer must be twice the number of arrangements got before interchanging the roles of $X$ and $Y$, right? Of course with the multiplication of $(3!)^3$ to the above quantity. Sep 13, 2017 at 7:46
• Also there are two ways to account for the fact that you start with $X$. First is to note that it's twice as many combos of $X$s and $Y$s. You can also say that $X$ is the nationality on the first chair, but then you have one slot less to put the remaining $Z$s in. In any case the result is $37584=174\times (3!)^3$. Sep 13, 2017 at 7:46
• @N.F.Taussig OK, do that - or otherwise the suggestion about inclusion-exclusion principle would be misleading... Sep 13, 2017 at 7:48

There are $9!$ ways to arrange nine individuals. From these, we must exclude those seating arrangements in which two people from the same country are seated in adjacent seats.

One pair of adjacent people: We have three ways to choose the nationality of the pair. We have $\binom{3}{2}$ ways to choose the people of that nationality who form the pair. We have $2$ ways to arrange the people within the pair. Finally, we have eight objects to arrange, the pair and the other seven people, so there are $$\binom{3}{1}\binom{3}{2}2!8!$$ such seating arrangements.

Two pairs of adjacent people: There are two possibilities, both pairs are from the same nationality (so the three people of that nationality sit in consecutive seats) or they are from different nationalities.

Both pairs are from the same nationality: We have three ways to choose the nationality that sits together and $3!$ ways to arrange the people of that nationality in a row. That leaves us with seven objects to arrange, the block of three people from one nationality and the other six people. Hence, we have $$\binom{3}{1}3!7!$$ such seating arrangements.

Two pairs from different nationalities: We have three ways to choose the nationalities from which the pairs are selected. In each case, we have $\binom{3}{2}$ ways to select two people of that nationality to sit together and $2$ ways to arrange them within the pair. That leaves us with seven objects to arrange, the two pairs and the five other people. Hence, there are $$\binom{3}{2}^32!^27!$$ such seating arrangements.

Three pairs of adjacent people: Again, we have two cases to consider. Either we have two pairs of one nationality and one pair from a different nationality or three pairs of different nationalities.

Two pairs from one nationality and one pair from a different nationality: We have three ways to select the nationality from which two pairs of adjacent people come, $3!$ ways to arrange the people of that nationality, two ways to choose the nationality of the remaining pair, $\binom{3}{2}$ ways to choose the members of that nationality who sit in adjacent seats, and $2$ ways to arrange those people within the pair. That leaves us with six objects to arrange, the block of three people of one nationality, the pair of another nationality, and the other four people. Hence, there are $$\binom{3}{1}3!\binom{2}{1}\binom{3}{2}2!6!$$ such seating arrangements.

Three pairs from different nationalities: We must choose two people from each nationality who sit in adjacent seats and arrange the two people within each pair. This leaves us with six objects to arrange, the three pairs and the other three people. Hence, we have $$\binom{3}{2}^32!^36!$$ such seating arrangements.

Four pairs of adjacent people of the same nationality: Again, we have two cases. Either there are two nationalities with two pairs of adjacent people or there is one nationality with two pairs of adjacent people and one pair of adjacent people from each of the other nationalities.

Two nationalities with two pairs of adjacent people: We choose two of the the three nationalities. Within each such nationality, all three people must be adjacent, so they can be arranged in $3!$ ways within their blocks. That leaves us with five objects to arrange, the two blocks of three people of one nationality and the other three people. Hence, there are $$\binom{3}{2}3!^25!$$ such seating arrangements.

One nationality with two pairs of adjacent people and two other nationalities with one pair of adjacent people: We have three ways of choosing the nationality from which two pairs of adjacent people are drawn and $3!$ ways of arranging the people of that nationality. For each of the other two nationalities, we have $\binom{3}{2}$ ways to choose two people of the same nationality to sit in adjacent seats and $2$ ways to arrange them within the pair. This leaves us with five objects to arrange, the block of three people of one nationality, the two pairs, and the other two people. Hence, there are $$\binom{3}{1}3!\binom{3}{2}^22!^25!$$ such seating arrangements.

Five pairs of adjacent people: We must have two nationalities with two pairs of adjacent people and one nationality with one pair of adjacent people. There are $\binom{3}{2}$ ways to choose the nationalities with two pairs of adjacent people. Since the three people of those nationalities must be adjacent, there are $3!$ ways to arrange the people of each of those nationalities. There are $\binom{3}{2}$ ways to choose two people from the third nationality who sit together and $2$ ways to arrange them within the pair. This leaves us with four objects to arrange, the two blocks of three people, the pair, and the remaining individual. Hence, we have $$\binom{3}{2}3!^2\binom{3}{2}2!4!$$ such seating arrangements.

Six pairs of adjacent people: We must have two pairs of adjacent people from each nationality. Hence, the three people of each nationality must be adjacent. We have $3!$ ways to arrange the nationalities and $3!$ ways to arrange the block of three people within each nationality. Hence, there are $$3!^4$$ such seating arrangements.

By the Inclusion-Exclusion Principle, there are $$9! - \binom{3}{1}\binom{3}{2}2!8! + \binom{3}{1}3!7! + \binom{3}{2}^32!^27! - \binom{3}{1}3!\binom{2}{1}\binom{3}{2}2!6! - \binom{3}{2}^32!^36! + \binom{3}{2}3!^25! + \binom{3}{1}3!\binom{3}{2}^22!^25! - \binom{3}{2}3!^2\binom{3}{2}2!4! + 3!^4$$

• Thanks for the detailed solution. I still have a question. Consider the case "One pair of adjacent people". Isn't $\binom{3}{1}\binom{3}{2}2!8!$ containing more than one pair of adjacent people? Since there might occur a pair in that $8!$ term. For example $XXYZZYZXY$ fits in this case right? Or should the naming of the case must be "at least one pair of adjacent people", and later this combination, $XXYZZYZXY$, is being cancelled out by the "at least two pair" case? Sep 13, 2017 at 8:45
• Is it just me or do it add up to a negative number?! Sep 13, 2017 at 9:00
• Yes, it is entirely possible that there may be more than one pair of adjacent people. We use the Inclusion-Exclusion Principle to eliminate over counting. For two sets, the Inclusion-Exclusion Principle states that $$|A \cup B| = |A| + |B| - |A \cap B|$$ since adding the number of elements of set $A$ and set $B$ counts those in $A \cap B$ twice, we must subtract the elements in $A \cap B$ so that we only count each element in $A \cup B$ once. Sep 13, 2017 at 9:00
• @skyking There was a factor of $3!$ missing in the third-to-last term (one nationality with two pairs of adjacent people and two nationalities with one pair of adjacent people). Thank you for alerting me to the error, which took me inordinately long to find given that I had included that factor in the justification for that term. Sep 13, 2017 at 15:01