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

Question

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

Answer 1

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

Answer 2

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$$