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?
Complementary Counting
I will assume the people are not identical
Find the number of ways in which they do form a consecutive block and then you can just subtract this number from the total.
I think it will run into a few cases:
Total number of ways in which americans form a block = 9!
Total number of ways in which russians form a block = 10!
Total number of ways in which chinese form a block = 8!
But we have counted some solutions multiple number of times.
Total number of ways in which russians and americans form a block = 7!
Total number of ways in which russians and chinese form a block = 6!
Total number of ways in which americans and chinese form a block = 5!
Total number of ways in which russians, americans and chinese form a block = 3!
So total number of ways: 9!+10!+8! - (7!+6!+5!) + 3! (You can also say ,"by principle of inclusion and exclusion")
Now subtract it from 12!
So
Answer:12! - (9!+10!+8! - (7!+6!+5!) + 3!)
I got 474975474 ways
P.S:I am most likely wrong. I find counting questions hard always. But I have tried working this problem. Tell me if you did not understand something, most likely the step is wrong
I do not think that either of the two replies is correct.
Let A be the event that all the Americans are together as a block. Then use R and C stand for the same for the other two groups. Now we want the number $\displaystyle \left| {A^c R^c C^c } \right|$, that is not A, not R and not C (none of the groups forms a single consecutive block).
You will want to justify each of the following.
The number of ways that all the American forms a single consecutive block is $\displaystyle \left| A \right| = \left( {4!} \right)\left( {9!} \right)$, WHY?.
The number of ways that all the American and all of the Russians are together as a consecutive block is $\displaystyle \left| AR \right| = \left( {4!} \right) \left( {3!} \right)\left( {7!} \right)$, WHY?.
The number of ways that at least one of the national groups forms a single consecutive block is:
$\displaystyle \left| {A \cup R \cup C} \right| = \left| A \right| + \left| B \right| + \left| C \right| - \left| {AR} \right| - \left| {AC} \right| - \left| {RC} \right| + \left| {ARC} \right|$.
Now you want $\displaystyle \left| {A^c R^c C^c } \right| = 12! - \left| {A \cup R \cup C} \right|$.