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

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*}$$


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.


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.

Tags:

Combinatorics

Recent Posts