number of ways of choosing $r$ points from $n$ points arranged in a circle such that no consecutive points is taken.

Question

number of ways of choosing $r$ points from $n$ ponts arranged in a circle such that no consecutive points is taken.

(I have seen some question on SE related to this. But I am trying to solve it using my own method).

Let the points be taken in a straight line $\{A_1,A_2,...,A_n\}$. I have to choose $r$ points such that no two points are consecutive. Let the chosen points be represented by $\{x_1,x_2,...,x_r\}$. The number of ways of choosing such points is same as the number of ways of placing these $r$ points among $n-r$ objects such that none of the points $\{x_1,x_2,...,x_r\}$ come together. Since I am only talking about "choosing" points, I will assume all the points to be identical.

This can be calculated by assuming gaps between the $n-r$ initial objects. There will be $n-r$ gaps since the leftmost gap and right most gap are same for a circular arrangement. First I will place $x_1$. The number of ways of placing the remaining $r-1$ points in $n-r-1$ gaps is $$^{n-r-1}C_{r-1}$$ (the points are assumed to be identical).

Similarly, If I start with $x_2$, the number of ways will be $$^{n-r-1}C_{r-1}$$

So the total will be $$n\cdot^{n-r-1}C_{r-1}$$

But the answer given is $$\frac{n\cdot^{n-r-1}C_{r-1}}{r}$$

Answer 1

There are several problems with your approach.

• It’s true that after you place $x_1$, there are $\binom{n-r-1}{r-1}$ ways to place the remaining $r-1$ points, but you’ve not taken into account the fact that there are $n-r$ different plces to put $x_1$.

• Each of the points $x_k$ gives rise to the same set of arrangements, so even if the $\binom{n-r-1}{r-1}$ figure were correct for the arrangements after you place $x_1$, you shouldn’t be multiplying by anything.

• Even if it were true that for each $x_k$ you get $\binom{n-r-1}{r-1}$ different arrangements, and different points $x_k$ gave you different arrangements, there are $r$ points $x_k$, not $n$, so the total number of different arrangements would be $r\binom{n-r-1}{r-1}$ arrangements, not $n\binom{n-r-1}{r-1}$.

Your approach can be made to work, but you have to be pretty careful. Imagine that the $n$ points are numbered clockwise from $1$ to $n$. Suppose that we list the gaps as $G_1,\ldots,G_{n-r}$ in clockwise order. There are $\binom{n-r}r$ ways to pick $r$ of these $n-r$ gaps for the points $x_1,\ldots,x_r$, which I’ll assume are listed in consecutive order clockwise. However, this overcounts. Specifically, we’re counting each choice of $r$ points $n-r$ times. This may be a little hard to see, so let me use a specific example. Suppose that we put $x_1$ in $G_1$, $x_2$ in $G_2$, and so on, finally putting $x_r$ in $G_r$. This means that there is one unchosen point between $x_1$ and $x_2$, one unchosen point between $x_2$ and $x_3$, and so on to one unchosen point between $x_{r-1}$ and $x_r$, with all of the remaining unchosen points between $x_r$ and $x_1$.

Now suppose instead that we put $x_1$ in $G_2$, $x_2$ in $G_3$, and so on, finally putting $x_r$ into $G_{r+1}$. This also means that there is one unchosen point between $x_1$ and $x_2$, one unchosen point between $x_2$ and $x_3$, and so on to one unchosen point between $x_{r-1}$ and $x_r$, with all of the remaining unchosen points between $x_r$ and $x_1$. In other words, we get exactly the same circular progression of chosen and unchosen points. The same is true no matter which gap gets $x_1$, provided that $x_2,\ldots,x_r$ are consecutively put into adjacent gaps clockwise. There are $n-r$ gaps, and we could start by putting $x_1$ into any of them, so there are $n-r$ ways to get exactly the same circular progression of chosen and unchosen points. And what’s true of the arrangement that we get when we put the chosen points into consecutive gaps is true of any other arrangement as well. Thus, we’re counting each arrangement $n-r$ times and need to divide by $n-r$. Doing so gives us

$$\frac1{n-r}\binom{n-r}r=\frac1r\binom{n-r-1}{r-1}\;.\tag{1}$$

Of course you know that this isn’t right, since it’s missing a factor of $n$; what have we missed?

The problem is that we’ve only established the relative positions of the chosen points: we know how many unchosen points there are between consecutive chosen points, but we don’t know whether the first chosen point is point $1$, point $n$, or something in between. Thus, each of the arrangements of chosen and unchosen points that we’ve counted actually corresponds to the $n$ different choices of $r$ points with the same spacing between adjacent chosen points. And that gives us the missing factor of $n$: there are really

$$\frac{n}r\binom{n-r-1}{r-1}$$

ways to choose the $r$ points.

If we cared only about the spacing of the chosen points and not about their absolute positions around the circle, we’d not need to make that last correction: $(1)$ would be the right number.

Answer 2

Choose an arbitrary point on the circle and "break" the circle in that point. The resulting configuration can be seen as a string of length $n$ over the alphabet $\Sigma=\{0,1\}$, with the properties:

• There are exactly $r$ characters "$1$";
• There are no consecutive "$1$"s;
• The first digit and the last character are not both "$1$".

If both the first character and the last one are "$0$", we are just expressing $n-r$ as a sum of $r+1$ positive integers, that represent the lengths of the blocks of zeroes. By stars and bars, there are $\binom{n-r-1}{r}$ strings of that kind. On the other hand, if the first character is zero while the last one is one, or the opposite, we are expressing $n-r$ as a sum of $r$ positive integers. It follows that the total number of our arrangements is given by:

$$\begin{eqnarray*} \binom{n-r-1}{r}+2\binom{n-r-1}{r-1} &=& \binom{n-r-1}{r-1}+\binom{n-r}{r}\\[0.2cm]&=&\color{red}{\frac{n}{n-r}\binom{n-r}{r}}\\[0.2cm]&=&\color{blue}{\frac{n}{r}\binom{n-r-1}{r-1}}.\end{eqnarray*}$$

Answer 3

Let us call the $r$ points engines $(E)$ and the rest bogies $(B)$

Looking clockwise, form $r$ trains of $[BE]$, then $(n-2r)\;\;B's$ are unattached.

Attach them to the trains using stars and bars in $\dbinom{n-r-1}{r-1}$ ways,

The first engine can be placed anywhere from $1$ to $n$ assuming a numbered circle, but each combination will be repeated $r$ times, so multiply by $\dfrac{n}{r}$

Answer 4

We to begin with label the positions to be filled $1,2,\cdots,r$ going around the circle in cyclic order, say counterclockwise. (These positions are not ordered in any way in the problem, we only introduce this cyclic ordering to facilitate a counting argument needed.)There must be gaps $g_k \ge 1$ between each labelled position and its two adjacent labelled positions. This gives the cyclic ordering $$g_1,1,g_2,2,\cdots,g_r,r.$$ Here the first gap $g_1$ serves as the gap between labelled position $r$ and labelled position $1.$ Now the sum of the $g_k$ is $n-r$ and since each is at least $1$ we may define $h_k=g_k-1$ so that $h_k \ge 0$ and the $h_k$ sum to $n-2r.$ To emphasize: this only represents a cyclic ordering, not the final positions of things.

Now we turn to counting how many solutions there are to $$h_1+h_2+\cdots+h_r=n-2r, \tag{1}$$ and note there are $r-1$ plus signs, so that using "stars and bars" we add the number of plus signs to the total $n-2r$ to get $(n-2r)+(r-1)=n-r-1.$ So (1) has $C(n-r-1,r-1)$ solutions, using $C(m,k)$ to mean the binomial coefficient.

Now let $A$ be our desired count of the number of placements of the $r$ things into the $n$ positions around the circle, where for this count the placed positions are considered as a subset, so are not ordered (cyclically or otherwise). It follows that a given situation counted in $A$ may be turned into one in which the placed positions are cyclically labelled in $rA$ ways, since one may choose any of the $r$ placed positions and call it $1$ inducing a cyclic ordering on the placed positions.

On the other hand, the binomial coeffficient which counts the solutions to $1$ will, if multiplied by $n$ to account for rotating the cyclic order into a definite one of the $n$ possible locations for it, also be the count for the number of placements of the $r$ things into their positions, where this time the cyclic ordering of those positions has already been done by the construction.

In sum, we get the equation $rA=nC(n-r-1,r-1),$ and dividing here by $r$ leads to the desired formula for the number $A$ of ways to select the $r$ positions around the circle havint $n$ positions in all.

Answer 5

Consider $n$ things in a circle namely $P_1,P_2 \dots P_n$. Without loss of generality let us assume that $P_1,P_2 \dots P_n$ are all arranged in a circle in a clockwise manner. Now let us start the question by counting the number of favourable cases always involving $P_1$. Clearly $P_2$ and $P_n$ cannot be selected now. as they are just adjacent to $P_1$. Therfore we can open the circle at $P_2$ and $P_n$ thus forming a linear arrangement with its end at $P_3$ and $P_{n-1}$. Now we can simply choose $r-1$ things out of these $n-3$ things so that no two are adjacent. By using the formula we will get $C^{n-r-1}_{r-1}$.

Now this was the case in which $P_1$ was definitely included. Similarly there will be cases where in $P_2$ is definitely included and so on up to the case where $P_n$ is definitely included. Thus there are $n$ such cases. Therefore we will be multiplying the answer we got by $n$. Therefore $n \cdot C^{n-r-1}_{r-1}$.

But careful!!! We have counted in excess. I will tell you how.

Let's consider a special case where in $n=9$ and $r=3$. Suppose I choose $P_1,P_3,P_5$ and so on cases where $P_1$ is definitely included. Now in the case where $P_3$ is definitely included also this case will appear. Also it will appear in the case where $P_5$ is definitely included. And so if you care to see the pattern will be repeated $3$ times. Therefore in selection of $r$ things the pattern repeats $r$ times. Therefore to get the correct answer we will have to divide it by $r$.

Hence, our final answer will be $\frac{n}{r} C^{n-r-1}_{r-1}$.

Also please note that the formula that I have used for the linear part in between has been already proved by you in the question itself.

Just have to plug in $n$ as $n-3$ and $r$ as $r-1$ and you have your answer....

Good Luck.
Best wishes.