Number of ways to seat nine people around circular table if no two people from the same country sit in adjacent seats

Question

Problem: Nine delegates, three each from three different countries, should be seated at a round table that seats nine people. How many different ways are there to seat them in such a way that no two delegates from the same country sit near each other? All the delegates are different, and arrangements that differ only by rotation are considered the same.

Solution: I've found a dull solution for the problem. You just fix some guy from one of the countries in the "first" place and build all possible correct arrangements. First you consider all the different ways two other guys from the same country can be placed. And after that one can just see that leftover places are split into one of the three possible groups $1 + 2 + 3$, $1 + 1 + 4$, $2+2+2$. For each of the splits you count number of ways to seat other delegates and thus find the answer. But this method involves drawing a lot of tables and seems like prettified brute force solution.

Question: is there another more elegant way of solving the problem? Statement reminds of Lovász local lemma, but this lemma gives only some bound for probability. May be there are some another theorem on coloring or something like this?

Thanks in advance for any ideas.

Answer 1

No ,you have to bruteforce in this case in order to get the solution. But if from a certain country, there had been only one person the you could straightaway apply linear permutation.

Answer 2

You can apply the Inclusion-Exclusion Principle.

Let's call the countries $A, B, C$. Let the delegates from country $A$ be $a_1, a_2, a_3$; let the delegates from country $B$ be $b_1, b_2, b_3$; let the delegates from country $C$ be $c_1, c_2, c_3$.

If there were no restrictions, we could seat delegate $a_1$ anywhere since we only care about the relative order of the delegates in a circular permutation. Relative to $a_1$, we can seat the remaining eight delegates in $8!$ ways as we proceed clockwise around the table. From these arrangements, we must subtract those arrangements in which a pair of delegates from the same country are adjacent.

A pair of delegates from the same country are adjacent: We have eight objects to arrange, the block of two delegates and the other seven people. Reserve any two adjacent seats for the block of two delegates. There are three ways to select the country with adjacent delegates, $\binom{3}{2}$ ways to select which two of the three delegates from that country are adjacent, $7!$ ways to arrange the other seven people in the remaining seven seats as we proceed clockwise around the table from the seats reserved for the two delegates in the block, and $2!$ ways to arrange the delegates within the block. Hence, there are $$\binom{3}{1}\binom{3}{2}7!2!$$ such seating arrangements.

Two pairs in which pairs of delegates from the same country are adjacent: There are two possibilities. Either both pairs are from the same country, in which case the three delegates from that country sit in adjacent seats, or the two pairs are from different countries.

Two pairs from the same country: We have seven objects to arrange, the block of three consecutive delegates from the same country, and the other six people. Reserve any three consecutive seats for the block of three delegates. There are $3$ ways to select the country whose delegates sit in consecutive seats, $6!$ ways to seat the remaining six people in the six remaining seats as we proceed clockwise around the table from the seats reserved for the block, and $3!$ ways to arrange the delegates within the block. Hence, there are $$\binom{3}{1}6!3!$$ such seating arrangements.

Two pairs from different countries: We have seven objects to arrange, the two blocks of adjacent delegates and the other five people. There are $\binom{3}{2}$ ways to select the two countries which have a pair of adjacent delegates, $\binom{3}{2}$ ways to select which two of the three delegates from each of those countries is adjacent, $6!$ distinguishable ways to arrange the seven objects around the table (up to rotation), and $2!$ ways to arrange the delegates within each block. Hence, there are $$\binom{3}{2}\binom{3}{2}\binom{3}{2}6!2!2!$$ such seating arrangements.

Three pairs in which delegates from the same country are adjacent: There are two possibilities. Either there are two pairs from one country and another pair from a different country or each of the three pairs is from a different country.

Two pairs from one country and one pair from a different country: We have six objects to arrange, a block of three consecutive delegates from one of the countries, a pair of adjacent delegates from another country, and the other four people. There are three ways to select the country from which all three delegates sit in consecutive seats, two ways to select a different country from which a pair of delegates will sit in adjacent seats, $\binom{3}{2}$ ways to select the delegates from that country who will sit in adjacent seats, $5!$ distinguishable ways to arrange the six objects around the table (up to rotation), $3!$ ways to arrange the three delegates from the same country who sit in the block of three consecutive seats, and $2!$ ways to arrange the two delegates from the second country who sit in the pair of two adjacent seats. Hence, there are $$\binom{3}{1}\binom{2}{1}\binom{3}{2}5!3!2!$$ such seating arrangements.

Each of the three pairs is from a different country: We have six objects to arrange, the three pairs and the other three people. There are $\binom{3}{2}$ ways to select the pair of adjacent delegates for each of the three countries, $5!$ distinguishable ways to arrange the six objects around the table (up to rotation), and $2!$ ways to arrange the two delegates within each block of consecutive seats. Hence, there are $$\binom{3}{2}\binom{3}{2}\binom{3}{2}5!2!2!2!$$ such seating arrangements.

Four pairs in which delegates from the same country are adjacent: There are two possibilities. There are two countries with two pairs of adjacent delegates or there is one country with two pairs of adjacent delegates and one pair of adjacent delegates from each of the other two countries.

Two countries with two pairs of adjacent delegates: This means we have two countries from which all three delegates sit in consecutive seats. Thus, we have five objects to arrange, the two blocks of three people and the other three people. There are $\binom{3}{2}$ ways to select the two countries from which all three delegates sit in consecutive seats. The five objects can be arranged in $4!$ distinguishable ways (up to rotation). Within each block, the three delegates from the same country can be arranged in $3!$ ways. Hence, there are $$\binom{3}{2}4!3!3!$$ such seating arrangements.

One country with two pairs of adjacent delegates and two countries with one pair of adjacent delegates: There are five objects to arrange, a block of three consecutive delegates from one of the countries, the two blocks of adjacent pairs of delegates from the other two countries, and the remaining two people. There are $3$ ways to select the country from which two pairs of delegates are selected, $\binom{3}{2}$ ways to select two of the three people from each of the other countries to be the adjacent delegates from those countries, $4!$ distinguishable ways to arrange the five objects around the table (up to rotation), $3!$ ways to arrange the three consecutive delegates within their block, and $2!$ ways to arrange each pair of adjacent delegates within their blocks. Hence, there are $$\binom{3}{1}\binom{3}{2}\binom{3}{2}4!3!2!2!$$ such seating arrangements.

Five pairs in which a pair of delegates from the same country are adjacent: For this to occur, there must be two countries with two pairs of adjacent delegates and a pair of adjacent delegates from the third country. We have four objects to arrange, the two blocks of three consecutive people from the same country, the pair of adjacent people from the third country, and the other person. There are $\binom{3}{2}$ ways to select the two countries from which all three people sit in consecutive seats, $\binom{3}{2}$ ways to select which two of the three delegates from the third country sit in adjacent seats, $3!$ distinguishable ways to arrange the four objects (up to rotation), $3!$ ways to arrange the three people within each block of three people, and $2!$ ways to arrange the pair of adjacent people within the block of two people. Hence, there are $$\binom{3}{2}\binom{3}{2}3!3!3!2!$$ such seating arrangements.

Six pairs in which a pair of delegates from the same country are adjacent: This can only occur if the delegates from each country sit in a block of three consecutive seats. Thus, we have three objects to arrange, the three blocks of three consecutive people from each country. The three objects can be arranged in $2!$ distinguishable ways around the table (up to rotation). The three people within each block can be arranged in $3!$ ways. Hence, there are $$2!3!3!3!$$ such seating arrangements.

By the Inclusion-Exclusion Principle, the number of admissible seating arrangements is $$8! - \binom{3}{1}\binom{3}{2}7!2! + \binom{3}{1}6!3! + \binom{3}{2}\binom{3}{2}\binom{3}{2}6!2!2! - \binom{3}{1}\binom{2}{1}\binom{3}{2}5!3!2! - \binom{3}{2}\binom{3}{2}\binom{3}{2}5!2!2!2! + \binom{3}{2}4!3!3! + \binom{3}{1}\binom{3}{2}\binom{3}{2}4!3!2!2! - \binom{3}{2}\binom{3}{2}3!3!3!2! + 2!3!3!3!$$