Skip to main content

IntMath forum | Counting and Probability - Introduction

Combinatorics [Solved!]

My question

5 Chinese, 5 Russians and 5 Mexicans are sitting in a row in such a way that the Chinese cannot be seated in the first 5 seats, the Russians cannot be seated in the 5 middle seats and the Mexicans cannot be seated in the last 5 seats. In how many different ways can they sit?

Relevant page

3. Permutations

What I've done so far

The only thing I can tell is that the total number of possible arrangements, without the restriction, is 15!/5!*5!*5! based on the 3rd theorem. But I don't know how to apply the restriction!

X

5 Chinese, 5 Russians and 5 Mexicans are sitting in a row in such a way that the Chinese cannot be seated in the first 5 seats, the Russians cannot be seated in the 5 middle seats and the Mexicans cannot be seated in the last 5 seats. In how many different ways can they sit?
Relevant page

<a href="/counting-probability/3-permutations.php">3. Permutations</a>

What I've done so far

The only thing I can tell is that the total number of possible arrangements, without the restriction, is 15!/5!*5!*5! based on the 3rd theorem. But I don't know how to apply the restriction!

Re: Combinatorics

Hi Alex

Let me get you started.

Let the row of seats be divided into 3 segments, which I'll call "NC" (for non-Chinese, "NR" (for non-Russians) and "NM" (for non-Mexicans).

NC NR NM
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

The Chinese can sit in any NR or NM chairs, the Russians in either NC or NM chairs, and Mexicans in NC and NR.

We need to regard the 5 Chinese as 1 "unit", the 5 Russians as 1 "unit", and the 5 Mexicans as 1 "unit'.

For each segment, the remaining 10 people need to be thought of as 6 "units" (the 5 people from one country who can sit anywhere in the remaining 10 chairs, plus 1 "unit" which is people from the other country segment that can only sit in 5 of the remaining chairs.

I think I got all that right!

Try to continue on from there.

Regards
Murray

X

Hi Alex

Let me get you started.

Let the row of seats be divided into 3 segments, which I'll call "NC" (for non-Chinese, "NR" (for non-Russians) and "NM" (for non-Mexicans).

<table class="tableex"><tr><td>NC</td><td>NR</td><td>NM</td></tr><tr><td>1 2 3 4 5</td><td>1 2 3 4 5</td><td>1 2 3 4 5</td></tr></table>

The Chinese can sit in any NR or NM chairs, the Russians in either NC or NM chairs, and Mexicans in NC and NR.

We need to regard the 5 Chinese as 1 "unit", the 5 Russians as 1 "unit",  and the 5 Mexicans as 1 "unit'.

For each segment, the remaining 10 people need to be thought of as 6 "units" (the 5 people from one country who can sit anywhere in the remaining 10 chairs, plus 1 "unit" which is people from the other country segment that can only sit in 5 of the remaining chairs.

I think I got all that right!

Try to continue on from there.

Regards
Murray

Re: Combinatorics

Murray

Alex did not respond. Let me have a go at the next step.

Let's consider the group of Chinese people first.

In the 5 seats in the NC segment, we can only have Russians or Mexicans. There are `(10!)/((10-5)!) = (10!)/(5!)` ways to arrange the Russians and Mexicans in this first segment of seats.

For the other 2 seat segments (NR and NM), the Chinese can sit anywhere in the 10 seats, so `(10!)/((10-5)!) = (10!)/(5!)` ways, the Russians can only sit in the NM seats (`5!` ways) and the Mexicans can only sit in the NR seats (also `5!` ways).

How am I going so far?

X

Murray

Alex did not respond. Let me have a go at the next step.

Let's consider the group of Chinese people first. 

In the 5 seats in the NC segment, we can only have Russians or Mexicans. There are `(10!)/((10-5)!) = (10!)/(5!)` ways to arrange the Russians and Mexicans in this first segment of seats.

For the other 2 seat segments (NR and NM), the Chinese can sit anywhere in the 10 seats, so `(10!)/((10-5)!) = (10!)/(5!)` ways, the Russians can only sit in the NM seats (`5!` ways) and the Mexicans can only sit in the NR seats (also `5!` ways).

How am I going so far?

Re: Combinatorics

task 1: 5 seats in the NC segment can be occupied by 10 people
this can be done in 10x9x8x7x6=10!/5!(=30240) ways
task 2: 5 seats in the RC segment can be occupied by 10 people
this can be done in 10!/5! ways
task 3: 5 seats in the MC segment can be occupied by 10 people
this can be done in 10!/5! ways
now by applying multiplication principle of counting because actual task is achieved when all task 1 task 2 task 3 occur
so number of different ways they can sit= 10!/5! x 10!/5! x 10!/5!.

X

task 1: 5 seats in the NC segment can be occupied by 10 people 
                            this can be done in 10x9x8x7x6=10!/5!(=30240) ways
task 2: 5 seats in the RC segment  can be occupied by 10 people
                                        this can be done in 10!/5! ways
task 3: 5 seats in the MC segment  can be occupied by 10 people
                                        this can be done in 10!/5! ways
now by applying multiplication principle of counting because actual task is achieved when all task 1 task 2 task 3 occur
so number of different ways they can sit= 10!/5! x 10!/5! x 10!/5!.

Re: Combinatorics

Hello, a few comments first:

I do not think that OP should have applied the third theorem from 3. Permutations in this Case. In this problem, each individual is unique so that theorem is does not apply.

I could not understand what Murray meant by, "For each segment, the remaining 10 people need to be thought of as 6 "units" (the 5 people from one country who can sit anywhere in the remaining 10 chairs, plus 1 "unit" which is people from the other country segment that can only sit in 5 of the remaining chairs."

I followed stephenB but could not turn that into an answer.

AkashRajput is wrong. 10!/5! x 10!/5! x 10!/5! is greater than 15!. 15! would be the number of ways 15 people could fill 15 seats without any restrictions. The answer here must be less than 15!.

For my answer I will use the segments and NC NR NM notation that Murray suggested.

I break the problem up into 6 Cases:
5 russians, 0 mexicans in the NC seats (Case 1)
4 russians, 1 mexicans in the NC seats (Case 2)
3 russians, 2 mexicans in the NC seats (Case 3)
2 russians, 3 mexicans in the NC seats (Case 4)
1 russians, 4 mexicans in the NC seats (Case 5)
0 russians, 5 mexicans in the NC seats (Case 6)

In each Case, I start by filling the NC seats, then the NR seats, then the NM seats.

Case 1: 5 russians, 0 mexicans in the NC seats:
5! ways to seat the russians in the NC seats
5! ways to seat the mexicans in the NR seats
5! ways to seat the chinese in the NM seats
=> (5!)^3 arrangements in Case 1.

Case 2: 4 russians, 1 mexicans in the NC seats:
5*5*5! ways to fill the NC seats
5*5! ways to fill the NR seats
5! ways to fill the NM seats
=> (5!)^3 * 5^3 arrangements in Case 2.

Case 3: 3 russians, 2 mexicans in the NC seats:
5*4*5*4*5! ways to fill the NC seats
5*4*5! ways to fill the NR seats
5! ways to fill the NM seats
=> (5!)^3 * 5^3 * 4^3 arrangements in Case 3.

Case 1 and Case 6 have the same number of arrangements.
Case 2 and Case 5 have the same number of arrangements.
Case 3 and Case 4 have the same number of arrangements.
So we can just multiply what we've come up with by 2.

So my answer is 2 * (5!)^3 * (1 + 5^3 + 5^3*4^3).

Sanity check: 2 * (5!)^3 * (1 + 5^3 + 5^3*4^3) / 15! is roughly 0.02. That seems reasonable to me.

X

Hello, a few comments first: 

I do not think that OP should have applied the third theorem from <a href="/counting-probability/3-permutations.php">3. Permutations</a> in this Case. In this problem, each individual is unique so that theorem is does not apply.

I could not understand what Murray meant by, <i>"For each segment, the remaining 10 people need to be thought of as 6 "units" (the 5 people from one country who can sit anywhere in the remaining 10 chairs, plus 1 "unit" which is people from the other country segment that can only sit in 5 of the remaining chairs."</i>

I followed stephenB but could not turn that into an answer. 

AkashRajput is wrong. 10!/5! x 10!/5! x 10!/5! is greater than 15!. 15! would be the number of ways 15 people could fill 15 seats without any restrictions. The answer here must be less than 15!.

For my answer I will use the segments and NC NR NM notation that Murray suggested.

I break the problem up into 6 Cases:
5 russians, 0 mexicans in the NC seats (Case 1)
4 russians, 1 mexicans in the NC seats (Case 2)
3 russians, 2 mexicans in the NC seats (Case 3)
2 russians, 3 mexicans in the NC seats (Case 4)
1 russians, 4 mexicans in the NC seats (Case 5)
0 russians, 5 mexicans in the NC seats (Case 6)

In each Case, I start by filling the NC seats, then the NR seats, then the NM seats.

Case 1: 5 russians, 0 mexicans in the NC seats:
5! ways to seat the russians in the NC seats
5! ways to seat the mexicans in the NR seats
5! ways to seat the chinese in the NM seats
=&gt; (5!)^3 arrangements in Case 1.

Case 2: 4 russians, 1 mexicans in the NC seats:
5*5*5! ways to fill the NC seats
5*5! ways to fill the NR seats
5! ways to fill the NM seats
=&gt; (5!)^3 * 5^3 arrangements in Case 2.

Case 3: 3 russians, 2 mexicans in the NC seats:
5*4*5*4*5! ways to fill the NC seats
5*4*5! ways to fill the NR seats
5! ways to fill the NM seats
=&gt; (5!)^3 * 5^3 * 4^3 arrangements in Case 3.

Case 1 and Case 6 have the same number of arrangements. 
Case 2 and Case 5 have the same number of arrangements. 
Case 3 and Case 4 have the same number of arrangements. 
So we can just multiply what we've come up with by 2.

So my answer is 2 * (5!)^3 * (1 + 5^3 + 5^3*4^3). 

Sanity check: 2 * (5!)^3 * (1 + 5^3 + 5^3*4^3) / 15! is roughly 0.02. That seems reasonable to me.

Reply

You need to be logged in to reply.

Related Counting and Probability questions

Counting and Probability lessons on IntMath

top

Search IntMath, blog and Forum

Search IntMath