Selecting things arranged around a circle

[Saitama]

Homework Statement

If n things are arranged in circular order, then show that the number of ways of selecting four of the things no two of which are consecutive is
$$\frac{n(n-5)(n-6)(n-7)}{4!}$$

Homework Equations

The Attempt at a Solution

My approach to the problem is that I first select the objects without any restriction and subtract those cases when 4 things are consecutive, 3 things are consecutive and 2 things are consecutive. If this isn't the correct approach, please ignore what I have written below and suggest the alternative.

Number of ways to select 4 things without any restriction: $\binom{n}{4}$

There are n ways for four things to be consecutive.

There are n(n-5) ways for 3 consecutive things. My logic behind this is that I first count the ways for 3 consecutive things and the last thing to selected must be from n-5 remaining things.

Now I feel that the trouble is caused due to the last case when two things are consecutive.

There are n ways to select groups of two consecutive things. Now the other two must be from n-4 things. Hence, $n\binom{n-4}{2}$ ways.

I have found the error in the last case but I am unable to exclude the duplicate selections. For example, I arrange 9 things represented by letters A,B,C,D,E,F,G,H and I respectively. Let's select AB and then EF. When we later on select EF and then AB, this selection is same. Likewise, there are many similar selection. I have no idea about removing these duplicate selections.

I hope I used the correct words.

Any help is appreciated. Thanks!

 

[D H]

Your confusion will be much reduced if you imagine cutting that circle at some point and straightening it out into a line. Any collection of four non-consecutive items on the circle will also be a set of four non-consecutive items on that line. The advantage of thinking about a linear arrangement is that the line gives you a definite starting point and a definite ending point. Can you determine the number of sets of four non-consecutive items that can be drawn from a group of n things arranged in a line?

You've over-counted by bit because not all of those non-consecutive groups drawn from a linear arrangement will be non-consecutive in a circular arrangement. The groups that contain both the very first and very last items in the linear arrangement make for a consecutive selection when arranged in a circle. So count those groups and subtract from your total.

 

[haruspex]

There is another way to think about these non-contiguous selection problems (they come up a lot). It involves associating each item chosen with a buffer of non-choosable items on one side (to the right, say). In this case, there'll be one unchoosable for each. The details can be non-obvious.
First, let's consider it as an ordered selection. We know we can divide by 4! at the end to fix that.
We pick the first item arbitrarily (n ways). This effectively breaks it into a line, as D H describes, but of n-2 (-2 because the leftmost position is already out of bounds).
For a given valid selection of r of the n-2, we can imagine deleting the empty position to the right of each selected one. This makes it look like an unconstrained selection of r from n-2-r. Do you see it from there?

Spoiler

Conversely, for any unconstrained selection of r items of n-2-r in a line, we can insert an empty position following each selection. This is a 1-1 correspondence, so the number of ways of choosing the r from n-2 validly is ^n-2-rC_r.

 

[Saitama]

Hi D H!

. Can you determine the number of sets of four non-consecutive items that can be drawn from a group of n things arranged in a line?

Can you please give me a few hints for this? I am completely clueless.

@haruspex: I appreciate the time you took to make your post but I am stuck at the very first statement. What does the following mean?

It involves associating each item chosen with a buffer of non-choosable items on one side (to the right, say).

I am sorry if I am being idiotic, this is the part of mathematics I hate the most. I am always stumped at such kind of problems no matter how hard I try. :(

 

[haruspex]

It involves associating each item chosen with a buffer of non-choosable items on one side (to the right, say). In this case, there'll be one unchoosable for each.

Ok, let me try to clarify that.
You are not allowed to choose two adjacent items. I can ensure that by treating each selection as affecting two adjacent positions: I choose the item in the left hand of the pair and disallow any subsequent choice of the right-hand of the pair. It's this unchoosable item I called a ' buffer'. (In other examples of such problems there may be more than one buffer item for each selected one.)

First, let's consider it as an ordered selection. We know we can divide by 4! at the end to fix that.
We pick the first item arbitrarily (n ways). This effectively breaks it into a line, as D H describes, but of n-2 (-2 because the leftmost position is already out of bounds).

So suppose the items are 1 .. 12, and without loss of generality I picked item 1 first. Item 2 is therefore disallowed, and we are left with items 3 to 12. But note we cannot actually pick item 12 because there is no buffer item available to its right.

For a given valid selection of r of the n-2, we can imagine deleting the empty position to the right of each selected one. This makes it look like an unconstrained selection of r from n-2-r. Do you see it from there?

So suppose we need to pick three more from 3..12, and we pick e.g. 5, 7, 10. This means 6, 8 and 11 are the corresponding buffer items. Compare this with picking 3 items from seven items (a to g) with no constraint on how we choose them. In particular, compare it with picking items c, d and g:

Buffered choice:  3 4 [B]5[/B] [I]6[/I] [B]7[/B] [I]8[/I] 9 10 [B]11[/B] [I]12[/I]
Free choice:      a b [B]c[/B]   [B]d[/B]   e  f  [B]g[/B]

Now here's the trick: for every valid buffered choice (in bold), I can construct a corresponding free choice from the smaller set by skipping the buffer items (in italics). (That's what the illustration above is supposed to show.) And likewise, for every free choice from the reduced set, I can generate a valid buffered choice by inserting a buffer item to the right. These two operations are inverses. This establishes a 1-1 correspondence between the two sets of choices, thus there are the same number of such choices.

 

[D H]

Hi D H!

Can you please give me a few hints for this? I am completely clueless.

I often take a reductionist approach to these problems: break the problem down into a simpler form. Others take a more holistic approach. I'll describe a reductionist approach.

First, some nomenclature. Define $S_L(n,m)$ as the number of non-consecutive subsets of size m that can be selected from a set of n items arranged in a line. Another way to look at this: We're going to draw m items from a set of n items numbers 1 to n such that order doesn't count (e.g., sets {1,3,6,8} and {3,6,8,1} are the same set) and such that the absolute value of difference between any pair of items in the set is two or more.

Now let's look at determining a formula for $S_L(n,m)$. First, some base cases. The case m=1 is simple. We don't have to worry about the problem of consecutiveness here. There are n ways to choose one item from a set of n. In other words, $S_L(n,m)=n$ if m=1.

Another base case is that given a collection size m, there's a lower limit on the size of the set n in order to construct even one subset that satisfies the non-consecutiveness constraint. There's no way to draw two non-consecutive items from a set of less than three items, three items from a set of less than five items, four items from a set of less than seven items, and so on. In other words, $S_L(n,m)=0$ if m>1 and n<2m-1.

The general case is m>1 and n≥2m-1. we can generate our subset of m items in two ways. One is to pick item #1 as our first item and pick a subset of m-1 items from items #3 to #n. This is the same as the problem of picking a subset of m-1 items from a set of n-2 items. If we don't pick item #1 as the first item, we have n-1 items left from which we still have to pick m items. In other words, $S_L(n,m)=S_L(n-2,m-1) + S_L(n-1,m)$.

Now we have a complete recursive formulation for $S_L(n,m)$:
$$S_L(n,m) = \begin{cases} n & m=1 \\ 0 & m>1, n<2m-1 \\ S_L(n-2,m-1) + S_L(n-1,m) & \text{otherwise} \end{cases}$$
See if you can take this from here.

 

[Saitama]

I can ensure that by treating each selection as affecting two adjacent positions: I choose the item in the left hand of the pair and disallow any subsequent choice of the right-hand of the pair. It's this unchoosable item I called a ' buffer'. (In other examples of such problems there may be more than one buffer item for each selected one.)

My English is poor so I would like to know if I understand your statements correctly.

From the statement "I can ensure that by treating each selection", which selection do you talk about? Selection of two adjacent objects or the non-adjacent ones?

Can you please explain "buffer" through a simple example? Let us consider numbers 1,2,3,4,5...15. If I select 2 and 5, then to satisfy the condition of non-consecutiveness (is that a word? :P), I cannot select 1,3,4 and 6. Which of the number you call "buffer"? Sorry if I am being annoying but honestly, I cannot remove the mind-block I have about the given problem.

Now we have a complete recursive formulation for $S_L(n,m)$:
$$S_L(n,m) = \begin{cases} n & m=1 \\ 0 & m>1, n<2m-1 \\ S_L(n-2,m-1) + S_L(n-1,m) & \text{otherwise} \end{cases}$$
See if you can take this from here.

D H, thanks a lot for explaining things so nicely. I understood most of the things you wrote but unfortunately, I don't know how to solve recursive relations. I am very sorry.

 

[haruspex]

From the statement "I can ensure that by treating each selection", which selection do you talk about? Selection of two adjacent objects or the non-adjacent ones?

I'm saying that if I pick one object then I will not pick the one next to it on its right.

Can you please explain "buffer" through a simple example? Let us consider numbers 1,2,3,4,5...15. If I select 2 and 5, then to satisfy the condition of non-consecutiveness (is that a word? :P), I cannot select 1,3,4 and 6. Which of the number you call "buffer"?

A buffer is something which keeps two things apart. A "buffer state" is a country between two other countries which, if they had a common border, would be forever fighting each other. A buffer on a train is a piston mounted at the end of each carriage to absorb shocks in emergency stops.
Yes, having chosen 2 and 5 you cannot select 1, 3, 4 or 6. But thinking of it that way makes it hard to analyse. Instead, give each chosen item a buffer on one side only. So 3 serves as the buffer for 2, if 2 is chosen; 6 as the buffer for 5, etc. So when you choose 2 that removes 2 and its buffer, 3, from the available selections. And of course you cannot choose an item if its buffer has already gone.

D H's reductionist approach is fine too, and at some stage you will learn how to handle recurrence relations. But I like to end up with some sense of why a formula is as it is. E.g. the symmetries of the cube form the group S₄, which becomes obvious when you realize they're equivalent to permutations of the 4 long diagonals. In the present problem, one might start off just calculating some simple cases and maybe spot what the general formula seems to be. That can give a clue as to how to map the problem into one where that formula is obviously right.

 

[Saitama]

I'm saying that if I pick one object then I will not pick the one next to it on its right.

A buffer is something which keeps two things apart. A "buffer state" is a country between two other countries which, if they had a common border, would be forever fighting each other. A buffer on a train is a piston mounted at the end of each carriage to absorb shocks in emergency stops.
Yes, having chosen 2 and 5 you cannot select 1, 3, 4 or 6. But thinking of it that way makes it hard to analyse. Instead, give each chosen item a buffer on one side only. So 3 serves as the buffer for 2, if 2 is chosen; 6 as the buffer for 5, etc. So when you choose 2 that removes 2 and its buffer, 3, from the available selections. And of course you cannot choose an item if its buffer has already gone.

haruspex, I understand buffer now but can you please use some simpler approach? I don't think I am capable enough of understanding such complicated approaches and that too in one of the topics I hate the most. Is it possible to continue with my initial approach? It looks to me that you think I am going through a course of Combinatorial mathematics. I guess Combinatorics wasn't the correct word. The practice sheet I am currently going through is titled "Permutations and Combinations". I have spent a lot of time in understanding your posts but it isn't doing me any good. Can we please drop this buffer approach? Should I post a pdf of problems so that you can have a better idea of what I am currently studying?

at some stage you will learn how to handle recurrence relations.

I highly doubt that I will ever come across this in the coming 5 months. I am preparing for an engineering entrance test and the syllabus includes what is taught to us in high school and there is no such thing called "recurrence" in the high school syllabus. But I think I will take a look over it once I have completed my syllabus.

Sorry but I am honestly lost and have made no progress on the problem so far. :(

 

[haruspex]

can you please use some simpler approach?

Sorry, I can only think of three approaches: D H's, mine, and special casing:
- n ways to pick the first
- n-3 ways to pick the second
- # ways to pick the third depends on the relationship between the first two. If they were only 1 apart then n-5; if more than 1 apart then n-6
- etc.

With only four to pick in total, that's just about manageable, but it's a lousy approach to the problem in general.

 

[Saitama]

I know its quite late to revive the thread but I have come across a nice method (which doesn't use recursions) to solve the problem of linear arrangement and I am thinking if the same could be extended to the circular arrangement.

Consider the attachment 1. Let's select 4 things out of $n$. I denote them with a blue line.

Let $a,b,c,d$ and $e$ denote the number of things between the selected ones. Then we have the condition, $a,e\geq 0$ and $b,c,d\geq 1$. Also:

$$a+b+c+d+e=n-4$$
Number of solutions to the above equation with the given constraints are ${n-3 \choose 4}$ which is our answer to the linear arrangement.

How do I extend this method to the circular arrangement?

If I follow the same procedure as above (attachment 2), I have the condition $a,b,c,d\geq 1$ and

$$a+b+c+d=n-4$$

The solutions to the above are ${n-5 \choose 3}$ and this is definitely incorrect.

I am thinking of following DH's advice in #2 but I am not sure how to implement it. :(

 

[haruspex]

I know its quite late to revive the thread but I have come across a nice method (which doesn't use recursions) to solve the problem of linear arrangement and I am thinking if the same could be extended to the circular arrangement.

Consider the attachment 1. Let's select 4 things out of $n$. I denote them with a blue line.

Let $a,b,c,d$ and $e$ denote the number of things between the selected ones. Then we have the condition, $a,e\geq 0$ and $b,c,d\geq 1$. Also:

$$a+b+c+d+e=n-4$$
Number of solutions to the above equation with the given constraints are ${n-3 \choose 4}$ which is our answer to the linear arrangement.

How do I extend this method to the circular arrangement?

If I follow the same procedure as above (attachment 2), I have the condition $a,b,c,d\geq 1$ and

$$a+b+c+d=n-4$$

The solutions to the above are ${n-5 \choose 3}$ and this is definitely incorrect.

This is essentially the same as my method, and you can convert the problem from a circle to a line the way you do above. But first, you have to remember that you are making the first choice, the one that breaks the circle, special. So you have to think of it as an ordered selection of four. Correspondingly, having broken it out into a line, you are making an ordered selection of three. So the number of ways is $\frac{(n-5)!}{(n-8)!}$. Since you had n ways for the first choice, that's $\frac{n(n-5)!}{(n-8)!}$ for the ordered choice of four. Finally, to convert it to an unordered choice, divide by 4!, giving the desired answer.

 

[Saitama]

This is essentially the same as my method, and you can convert the problem from a circle to a line the way you do above. But first, you have to remember that you are making the first choice, the one that breaks the circle, special. So you have to think of it as an ordered selection of four. Correspondingly, having broken it out into a line, you are making an ordered selection of three. So the number of ways is $\frac{(n-5)!}{(n-8)!}$. Since you had n ways for the first choice, that's $\frac{n(n-5)!}{(n-8)!}$ for the ordered choice of four. Finally, to convert it to an unordered choice, divide by 4!, giving the desired answer.

I am not getting why you are considering the ordered selections.

If I break the circular arrangement at some point, then I have a situation as shown in the attachment.

$$a+b+c+d=n-4$$

With the constraint $a,b,c,d\geq 1$, the solutions to the above equation are $\dfrac{(n-5)!}{(n-8)!3!}$.

 

[haruspex]

If I break the circular arrangement at some point, then I have a situation as shown in the attachment.

You broke the circle by making your first selection (n ways). You then obtained a formula for making three unordered selections from what remains. But this is not the same as making four unordered selections. Your first selection is special.
One way to resolve that is to ask how many ways you can make an ordered selection of four from the n. So now you make the first selection, and an ordered selection of the remaining three. This gives the right answer for four ordered selections. Finally, divide by 4! for four unordered.

 

[Saitama]

But this is not the same as making four unordered selections. Your first selection is special.

Yes, I understand the first selection is special and there n ways for the first selection.

One way to resolve that is to ask how many ways you can make an ordered selection of four from the n.

I can find the ordered selection of four from n but I don't see why should I be doing that here. Can you please give an example to show why the unordered selection fails?

If I continue with what I wrote above, I have to simply multiply by $n$ and divide by 4. Multiplying by $n$ makes sense because the first selection is special but I can't see why I need to divide by 4. :(

 

[haruspex]

Multiplying by $n$ makes sense because the first selection is special but I can't see why I need to divide by 4. :(

Your procedure picked one from n, then 3 from n-1. This makes picking A, say, then {B, C, D} different from picking B then {A, C, D}. So you have effectively counted every valid selection {A, B, C, D} four times.

 

[Saitama]

Your procedure picked one from n, then 3 from n-1. This makes picking A, say, then {B, C, D} different from picking B then {A, C, D}. So you have effectively counted every valid selection {A, B, C, D} four times.

Very nicely explained, thanks haruspex! I finally understand this now.

Sorry for the so long delay.