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

- January 10th 2008, 01: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?

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

=166320-27

=166293

I not sure.... - January 10th 2008, 06: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 :)* - January 10th 2008, 08:47 AMwingless
- January 10th 2008, 08: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 , 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 , WHY?.

The number of ways that all the American and all of the Russians are together as a consecutive block is , WHY?.

The number of ways that__at least one__of the national groups forms a single consecutive block is:

.

Now you want .