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?

Printable View

- Jan 10th 2008, 12:41 AMascways
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?

- Jan 10th 2008, 04:10 AMSengNee
(12C4)(8C3)(5C5)-(9C1+10C1+8C1)

=166320-27

=166293

I not sure.... - Jan 10th 2008, 05:40 AMIsomorphism
Complementary Counting :D

I will assume the people are not identical ;)

Find the number of ways in which theyform a consecutive block and then you can just subtract this number from the total.__do__

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 :)* - Jan 10th 2008, 07:47 AMwingless
- Jan 10th 2008, 07:50 AMPlato
I do not think that either of the two replies is correct.

Letbe the event that all the Americans are together as a block. Then use**A**and**R**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**C****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|$.