# ways

• Jan 10th 2008, 01:41 AM
asc
ways
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, 05:10 AM
SengNee
(12C4)(8C3)(5C5)-(9C1+10C1+8C1)
=166320-27
=166293

I not sure....
• Jan 10th 2008, 06:40 AM
Isomorphism
Quote:

Originally Posted by asc
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 :D

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 :)
• Jan 10th 2008, 08:47 AM
wingless
Quote:

Originally Posted by Isomorphism
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!

They must be 9! 4!, 10! 3! and 8! 5!. You took americans as a group but probably forgot that there are 4! american groups. Same goes for all.
• Jan 10th 2008, 08:50 AM
Plato
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 $\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 $\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 $\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:
$\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 $\left| {A^c R^c C^c } \right| = 12! - \left| {A \cup R \cup C} \right|$.