[Math] How many ways are there to arrange 4 Americans, 3 Russians, and 5 Chinese into a queue, using inclusion-exclusion principle

discrete mathematicsinclusion-exclusion

How many ways are there to arrange 4 Americans, 3 Russians, and 5
Chinese into a queue, in such a way that no nationality forms a single consecutive block?

Let $A$ be the collection of ways that $4$ Americans forms a single consecutive block.
Similarly for $R$ and $C$. Notice that $A$ has $9 × 4! × 8!$ ways, and $R$ has $10 × 3! × 9!, C$ has $8 × 5! × 7!$ ways. We next use inclusion-exclusion. To calculate, for instance, $A \cap R$, we can first find the positions for the first person in $A$ and the first person in $R$, which will give $ 6+5+4+4+4+4+4+5+6= 42$ ways. Thus $ A \cap R$ has 42 × 4! × 3! × 5! ways. Similarly for $A \cap C, R \cap C\ and\ A \cap R \cap C.$

I can easily apply the inclusion-exclusion principle in problems such as:
The tennis club has 20 members, the stamp collectors have 15 and the Egyptology club has 8. Among the Egyptologists, there are two of the tennis players and three of the stamp collectors. Six people play both tennis and collect stamps. One eager person participates in all three clubs. How many people are engaged in the club life of E.?

Or such:

Use the inclusion-exclusion principle determine the number of
permutations of the 26 letters of the English alphabet that do not contain any of the strings $fish, rat, bird.$

But the first problem made no sense whatsoever to me. Can someone explain where the first $9 × 4! × 8!$ came from and maybe present the problem in another way so that i can understand?

Best Answer

Here's maybe a more helpful way to think through how these numbers are obtained.

To compute $A$, imagine the American block is just another person to be arranged among the $8$ others. Then we have $9$ "people," giving $9!$ arrangements. We must then multiply by $4!$ to arrange the Americans within the block.

For $A \cap R$, we have $7$ "people" (5 actual people and 2 blocks), giving $7!$, multiplied by $4! \cdot 3!$ to arrange within the blocks.

Similarly, for $A \cap R \cap C$, we must arrange the 3 blocks ($3!$) and then arrange within the blocks ($4! \cdot 3! \cdot 5!$)