IntMath Home » Forum home » Counting and Probability - Introduction » Combinatorics

Combinatorics [Pending...]

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?

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?

Reply

You need to be logged in to reply.