Selecting 3 persons sitting round a table

[Saitama]

Homework Statement

There are n persons sitting round a table. Prove that the number of different ways in which 3 persons can be selected so that no two are neighbours is $\frac{1}{6}n(n-4)(n-5)$.

Homework Equations

The Attempt at a Solution

I don't really know how to tackle this problem. I started with considering a simpler case first. Let the number of persons be 6.

We select one person from 6. Then according to given condition, we cannot select the two persons sitting just next to our selected person. So the other two must be selected from the remaining three. We have to subtract the cases when two nearby persons are selected when we selected two persons from the remaining three. Hence, number of cases=6C1*3C2-2=16, but this wrong because if we substitute 6 in the given formula (which we have to prove), it gives 2.

Any help is appreciated. Thanks! :)

 

[mfb]

With 6 persons (ABCDEF), and if the order does not matter, you just have two options: ACE and BDF.

6C1*(3C2-2)=6 - if you take into account that 3 choices of the first person will lead to the same set, you get the correct result of 6/3=2. That is a complicated way to calculate it, however.

I don't really know how to tackle this problem.

You could consider the problem with 1 person and with 2 persons, first.

 

[Saitama]

6C1*(3C2-2)=6 - if you take into account that 3 choices of the first person will lead to the same set...

Can you please elaborate this?

You could consider the problem with 1 person and with 2 persons, first.

The number of cases are zero for n=1 to 5.

 

[mfb]

Can you please elaborate this?

Real sets: ACE, BDF, in total 2 sets.
What you select: A+(CE), B+(DF), ..., F+(BD) in total 6 sets. You count each solution three times.

The number of cases are zero for n=1 to 5.

I mean the number of possibilities to select 1 (or 2) out of some general number n.

 

[Saitama]

Real sets: ACE, BDF, in total 2 sets.
What you select: A+(CE), B+(DF), ..., F+(BD) in total 6 sets. You count each solution three times.

I am still trying to understand this, meanwhile I will try the other questions you asked me.

To select one person, number of cases equals nC1.

For two persons, it is nC2. Are these correct?

 

[mfb]

It is correct for 1 person, but not for 2. Don't forget that the 2 cannot sit next to each other.

 

[Saitama]

It is correct for 1 person, but not for 2. Don't forget that the 2 cannot sit next to each other.

Is it nC2-n?

 

[mfb]

That is right.
I think would choose a different approach (begin with the case "select 1 person" and develop "select 2 persons" based on that), otherwise it could be tricky (but possible) to extend this to 3 persons.

 

[Saitama]

That is right.
I think would choose a different approach (begin with the case "select 1 person" and develop "select 2 persons" based on that), otherwise it could be tricky (but possible) to extend this to 3 persons.

I am still not sure how would I do it for three persons.

When three persons are selected without restriction, cases are nC3.
Subtracting those cases when three persons sitting next to each other are selected i.e. n
Now I need to subtract those when two out of three persons are sitting next to each other but how am I supposed to this?

 

[Dick]

I am still not sure how would I do it for three persons.

When three persons are selected without restriction, cases are nC3.
Subtracting those cases when three persons sitting next to each other are selected i.e. n
Now I need to subtract those when two out of three persons are sitting next to each other but how am I supposed to this?

Count seating possibilities for each person in turn. The first person can sit anywhere, so that's n possibilities. That leaves (n-3) possibilities for the second person. But now the case for the third person is a little complicated. It depends on whether the second person is one seat away from the first person or not. So break the (n-3) into those two cases.

 

[mfb]

Now I need to subtract those when two out of three persons are sitting next to each other

That is possible.

but how am I supposed to this?

Similar to the problem to choose 2 persons who do not sit next to each other.

 

[Saitama]

Similar to the problem to choose 2 persons who do not sit next to each other.

Count seating possibilities for each person in turn. The first person can sit anywhere, so that's n possibilities. That leaves (n-3) possibilities for the second person. But now the case for the third person is a little complicated. It depends on whether the second person is one seat away from the first person or not. So break the (n-3) into those two cases.

I am still a bit lost. Here's what I think. When the third person sits near the second person, the cases are n*(n-3)*2 and when the third person is not sitting near the third person, the cases are n*(n-3)*(n-5). Looks correct?

 

[mfb]

When the third person sits near the second person, the cases are n*(n-3)*2

You do not always have two places next to the second person which are not next to the first one. Try to place two at the same time, and add the third.

and when the third person is not sitting near the third person

 

[Saitama]

You do not always have two places next to the second person which are not next to the first one. Try to place two at the same time, and add the third.

I don't think I understand your second statement.

When the second person does not sit on the two nearest seats of the first person and the third person sits near the second person, i.e n*(n-5)*2 and when the third person does not sit near the second person, it is n*(n-5)*(n-8). I think this is still wrong. Sorry if I am acting like a dumb. -_-

Sorry, I meant second there.

 

[mfb]

I am confused by those incremental changes to previous statements. Can you use Dick's approach and write everything in one post, please?

 

[verty]

I have come up with a way to simplify this problem by removing the complexity of the seats being nonadjacent. If one seat can be treated as a group of 3 seats, the middle seat being occupied, the problem can be related to one in which the selections are allowed to be adjacent.

This approach can scale to selecting 4 or more seats in a awkward but obvious way.

 

[Dick]

I am still a bit lost. Here's what I think. When the third person sits near the second person, the cases are n*(n-3)*2 and when the third person is not sitting near the third person, the cases are n*(n-3)*(n-5). Looks correct?

You just aren't counting very carefully. What's you reasoning on that? I would say if the second person is sitting close it's n*2*(n-5). Count that out. Explain why I think so.

 

[haruspex]

I have come up with a way to simplify this problem by removing the complexity of the seats being nonadjacent. If one seat can be treated as a group of 3 seats, the middle seat being occupied, the problem can be related to one in which the selections are allowed to be adjacent.

This approach can scale to selecting 4 or more seats in a awkward but obvious way.

Maybe I misunderstand your suggestion, but it sounds like that would ensure a gap of two between two occupied seats. How about considering the seating of one person as taking out two adjacent seats (the occupied one being always the one to the left, say)?
After seating one arbitrarily, it now looks like a row of n-2 seats. It's pretty easy from there.

 

[verty]

Maybe I misunderstand your suggestion, but it sounds like that would ensure a gap of two between two occupied seats. How about considering the seating of one person as taking out two adjacent seats (the occupied one being always the one to the left, say)?
After seating one arbitrarily, it now looks like a row of n-2 seats. It's pretty easy from there.

So your first step is to select a group of 2, and your final step is to account for rotational symmetry? This is more elegant than what I did.

I thought about selecting from a row instead of a circle. In this case, one overcounts when both ends of the row are occupied. So the formula here will be a difference of two quantities. But it turns out those quantities are surprisingly simple.

I think we should let Pranav-Arora solve the problem now in the way that Dick suggests.

 

[Saitama]

Sorry everyone for the late reply. I couldn't reply the last time I was online as it was getting late night and yesterday I had a test so I couldn't access PF.

I will again try the Dick's suggestion of breaking (n-3) into two cases.

Case 1st: When the second person is one seat away from the first one, there are two possibilities. The third person cannot sit between the first and second person as I have already counted that case, so it leaves only one possibility for third person. So the cases are: n*2*1.

Case 2nd: When the second person is not one seat away i.e the second person sits on the remaining n-5 seats, the third person can sit on any of the two seats next to the second person i.e 2 possibilities. Total cases: n*(n-5)*2

Is this correct? I hope I explained my point correctly. Sorry for the poor English. =_=

PS: Congrats mfb!

 

[mfb]

Thanks.

Case 1st: When the second person is one seat away from the first one, there are two possibilities. The third person cannot sit between the first and second person as I have already counted that case, so it leaves only one possibility for third person. So the cases are: n*2*1.

Why just 1?
I am not sure if I understand what your cases are.

 

[Saitama]

Why just 1?
I am not sure if I understand what your cases are.

Okay, I will try to explain my thinking through images. Consider 6 people sitting round the table.

We need to count those cases when two out of three persons sit together. The first person can sit at any of the six places.

For the case 1st in my previous post, when the second person is one seat away (consider that first person is at A), he can sit on the seats circled by blue. As the third person should sit near the second but not near the first, he can sit on the seat circled by orange.

This gives me a total of 12 arrangements. If I plug n=6 in n*2*1, it is equal to 12. I don't see how this is wrong.

Also, I feel that I need to divide the result by 2 because A+(CD) is same as A+(ED).

Did I explain it correctly this time?

 

[verty]

Did I explain it correctly this time?

Placing that second person is annoying because the third person may or may not have a seat. With a bigger table, the third person can always be seated, so I would consider a table with 7 or more seats instead. And remember we don't know how many seats there are, so don't put actual numbers in the formula where n's should appear.

 

[Saitama]

Placing that second person is annoying because the third person may or may not have a seat. With a bigger table, the third person can always be seated, so I would consider a table with 7 or more seats instead. And remember we don't know how many seats there are, so don't put actual numbers in the formula where n's should appear.

For now I am considering only those cases when the second person is one seat away from the first. So I think its better to put some values of n and see if my thinking is correct. :)

 

[Dick]

Did I explain it correctly this time?

Yes, 6*2*1=12 ways. But if the three people selected are A, E and C then the 12 counts selections of them in different orders as different. You don't really care what order. You need to divide by something.

 

[mfb]

Consider 6 people sitting round the table.

Why do you use n, if you consider n=6 only?

For now I am considering only those cases when the second person is one seat away from the first.

You mean with 1 seat between them?

I agree with verty, please use a bigger table if you want to use specific n (and give those n!).

 

[Saitama]

Yes, 6*2*1=12 ways. But if the three people selected are A, E and C then the 12 counts selections of them in different orders as different. You don't really care what order. You need to divide by something.

Divide by 2?

Is this correct for n people too? I mean, for n people would there be n*2*1/2 ways?

Why do you use n, if you consider n=6 only?

I don't consider n=6 only, I used it in my previous post just to explain my thinking. Sorry if that confused you more.

You mean with 1 seat between them?

Yes.

I agree with verty, please use a bigger table if you want to use specific n (and give those n!).

For n too, its n*2*1/(something), I don't see how this is wrong.

 

[Dick]

Divide by 2?

Is this correct for n people too? I mean, for n people would there be n*2*1/2 ways?

Why divide by 2?? How many ways can you order 3 people? And no, it's not n*2*1 for any n. Why would you think that? And once you get this case, don't forget there is another one.

 

[Joffan]

I think you should NOT consider n=6, because the table is too crowded. Save it for a test case after you have the general formula, and see why it works in that case. Try say n=9 instead.

To place the first person (in ordered fashion for now), there are n options of course.

To place the second person - how many options?

To place the third person - how many options? (two distinct cases based on the second person's location - you will need the probabilities of each).

Then divide out the repeated possibilities (because this is not ordered selection).

 

[Yukoel]

Hello Pranav,
You can skip the casework too.Just notice that after selecting all the persons required(=3) you are left with n-3 persons and they are distributed in the gaps between adjacent members (there are 3 gaps too right?) ,each gap being nonempty.So you are left with the job of calculating the number of ways in which you can distribute n-3 things in 3 groups with each being non empty .How many ways are there to do this? Now to make such a selection you need to have chosen how many members before?(Thing is that there are n different persons.) .The constant is just a consequence of counting the same thing again in this method.Can you guess what it is?
Please correct me if I am wrong.
Regards
Yukoel

 

[mfb]

I think the approach with the gaps gives casework elsewhere, as you have to fit that "gap pattern" to the table. (3,3,3) in the gaps (on a table of 12) give 4 options, (3,3,4) in the gaps (on a table of 13) give 13 options, ...

 

[Yukoel]

I think the approach with the gaps gives casework elsewhere, as you have to fit that "gap pattern" to the table. (3,3,3) in the gaps (on a table of 12) give 4 options, (3,3,4) in the gaps (on a table of 13) give 13 options, ...

Hello mfb,
I think we can skip the casework too .I meant that one can see the remaining n-3 members have to be distributed after selecting the 3 required.(So as to fit in the table).Selecting just one member allows for the gaps to be numbered according to the number of elements within(As you say like 3,3,3 or 3,4,4 )(I am sticking to counting the gaps anticlockwise).Then I am thinking of the usage of the formula for distribution of say k objects into r groups so that none remains empty. This method can be used for more than 3 persons to be selected as well(r changes).
Am I wrong in here?
Please do tell. Thanks in advance.
Regards
Yukoel

 

[mfb]

If you select 3, you are done. The seating order of the members is fixed. You can select 1 and treat (3,4,3) and (3,3,4) as different cases afterwards. Hmm... that does work without case-by-case analysis, but then you have to evaluate a sum over n summands.

 

[verty]

Hello mfb,
I think we can skip the casework too .I meant that one can see the remaining n-3 members have to be distributed after selecting the 3 required.(So as to fit in the table).Selecting just one member allows for the gaps to be numbered according to the number of elements within(As you say like 3,3,3 or 3,4,4 )(I am sticking to counting the gaps anticlockwise).Then I am thinking of the usage of the formula for distribution of say k objects into r groups so that none remains empty. This method can be used for more than 3 persons to be selected as well(r changes).
Am I wrong in here?
Please do tell. Thanks in advance.
Regards
Yukoel

When n = 6, we have only 111 with 4 copies. I mean, we have 6 ways to select the first seat, but 4 are copies with this pattern. When n = 7, we have 112 with 0 copies. When n = 8, 113 and 122 with 0 copies.

When 3 divides n - 3, we get a pattern with copies, 111 or 222 when n = 9. So you have to subtract these I think.

 

[mfb]

4 copies? Do you mean 3?

When 3 divides n - 3, we get a pattern with copies, 111 or 222 when n = 9. So you have to subtract these I think.

Hmm, well, it is possible.

 

[verty]

4 copies? Do you mean 3?

Only 2 should be counted, is what I meant. When n=6, we have ACE or BDF, even if C was selected.

 

[haruspex]

Guys, this problem really isn't that hard.
As I said in post #18, consider each person as taking two adjacent seats, keeping a vacant seat to the left, say. The first pair can go in n positions. That leaves a line of n-2 seats, numbered 1 to n-2 from the left, say. In how many places can the leftmost of the remaining two pairs go, remembering to leave space for the last pair? If they take seats 1 and 2, how many choices for the last pair? If they take seats r and r+1, how many choices for the last pair?

 

[Dick]

Guys, this problem really isn't that hard.
As I said in post #18, consider each person as taking two adjacent seats, keeping a vacant seat to the left, say. The first pair can go in n positions. That leaves a line of n-2 seats, numbered 1 to n-2 from the left, say. In how many places can the leftmost of the remaining two pairs go, remembering to leave space for the last pair? If they take seats 1 and 2, how many choices for the last pair? If they take seats r and r+1, how many choices for the last pair?

Pretty much what I've been saying from the beginning. The direct way actually easy if you just break into two cases depending on where the second person is seated.

 

[Yukoel]

If you select 3, you are done. The seating order of the members is fixed. You can select 1 and treat (3,4,3) and (3,3,4) as different cases afterwards. Hmm... that does work without case-by-case analysis, but then you have to evaluate a sum over n summands.

Well can't we just use (n-3-1)C(3-1) ?(The number of distributing n things in r groups with each of the being nonempty is (n-1)C(r-1) )Here n=n-3 and r=3.

When n = 6, we have only 111 with 4 copies. I mean, we have 6 ways to select the first seat, but 4 are copies with this pattern. When n = 7, we have 112 with 0 copies. When n = 8, 113 and 122 with 0 copies.

When 3 divides n - 3, we get a pattern with copies, 111 or 222 when n = 9. So you have to subtract these I think.

Maybe I misunderstand the problem but the people are treated as distinct right?
So the copies of the same would be for n=6
ACE;CEA;and EAC(The counting is done clockwise only and so is the choosing of gaps).Hence there are three copies of the same thing right? Well yes one can subtract the overcounted things or maybe divide it as well by 3.What I am saying is to fix the first member on the circle and proceed anticlockwise through it with gaps.I do not understand the case with n=7 'cause each single choice has 3 copies.(Something like ACE again)
For n=9 111 doesn't fit on the table so it isn't equivalent to 222 which does fit.Is this wrong ?
Please do tell.
Thanks
Yukoel

 

[verty]

Maybe I misunderstand the problem but the people are treated as distinct right?

Too much thinking for me, sorry. I don't like how the sum depends on n. Let's leave it.

Using cases is definitely quickest. I guess this is a general principle - try cases first.

 

[Saitama]

I was confused by so many replies so I did not reply for sometime but I did figure it out. It will be difficult for me to put it in words but I will try my best.

Selecting three persons without restriction, nC3.
When three persons are sitting together, there are n ways.
In the last case, when two persons are sitting together, there can be n ways to select two persons sitting next to each other and the last person could sit at any of (n-4) places as he cannot sit near any of the two persons.

Hence, total ways=nC3-n-n*(n-4). Solving, I do end up with a right answer.

Thank you everyone!