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?

  • 2
    $\begingroup$ Explanation for the $9\times 4!\times 8!$: You have to compute how many arrangements have the 4 americans together. Then can be in any order among themselves, and there are $4!$ such ways. You don't care about the other nationalities, and whether they are together or not. There are thus $8!$ ways to arrange them. Finally, you need to fit in your block of americans into a gap in the random order of non-americans you have. There are $9$ such spaces, and so you multiply by $9$. I'm not sure about how to present the problem in a different way, which is why this is not an answer. $\endgroup$ – John Doe Jan 21 '18 at 14:40
  • 1
    $\begingroup$ $A$ is the collection of ways with the block of Americans together; $R$ is the collection with the Russian block together; $A \cap R$ is the collection of ways which fit both criteria, I.e., both the American and the Russian blocks are together. Does this help explain the relevance of inclusion-exclusion here? $\endgroup$ – Y. Forman Jan 21 '18 at 14:46
  • $\begingroup$ @Y.Forman I understand the groups and the intersections but not the numbers. :( $\endgroup$ – user481197 Jan 21 '18 at 14:50
  • 1
    $\begingroup$ @AbdulMalekAltawekji Ah, then does John Doe's comment help? $\endgroup$ – Y. Forman Jan 21 '18 at 14:51
  • $\begingroup$ @Y.Forman It cleared a bit of the stuff that I didn't grasp but I also don't get how $A \cap R$ is computed and i don't understand what $A \cap R \cap C$ would be $\endgroup$ – user481197 Jan 21 '18 at 14:55

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


Your Answer

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