# Number of ways to select $r$ objects from $n$ objects placed on the circumference of a circle

Prove using combinatorial argument that number of ways to select $$r$$ objects from $$n$$ distinct objects such that no two selected objects are consecutively placed on the circumference of a circle is $$\frac{n}{n-r} \binom{n-r}{r}.$$

I am aware that number of ways to do so is $$\frac{n}{r}\binom{n-r-1}{r-1}.$$ But I would want to understand how $$\frac{n}{n-r} \binom{n-r}{r}$$ comes combinatorially. I think it has something to do with menage problem.

• If $r > n/2$, then your formula gives zero. For instance, if $n = 3$ and $r = 2$, your formula gives $3\binom{1}{2} = 0$. Nov 11 '17 at 19:30
• Why would placing the objects on a circle affect the number of ways of selecting the objects?
– Jens
Nov 12 '17 at 0:00
• Your formulas do not make sense. Please check the wording of the question. Nov 12 '17 at 10:23
• You are right. I am editing. Nov 12 '17 at 11:29
• In my response to this question, I explain how to derive a formula for the number of selections of $k$ objects from $n$ objects arranged in a circle if no two of the $k$ objects are consecutive. With a bit of algebraic manipulation (using Pascal's Identity) of the formula I derived, you can derive the formula $$\frac{n}{k}\binom{n - k - 1}{k - 1}$$ and then show it is equivalent to the formula $$\frac{n}{n - k}\binom{n - k}{k}$$ Nov 12 '17 at 22:05

Let the objects be placed on the vertices of an $$n$$-gon. You ask how many ways are there to select $$r$$ of the objects such that no two selected objects are consecutive.
Your problem is equivalent to the problem of placing $$r$$ non-overlapping dominoes on the vertices of an $$n$$-gon. (Each domino covers two vertices.) To map the domino problem to your problem, let the object sitting on vertex $$i$$ be one of the selected ones. Then place one of the dominoes so that it covers vertices $$i$$ and $$i+1$$, with $$i+1$$ computed mod $$n$$. The condition that no two selected objects be consecutive is equivalent to the condition that the dominoes be non-overlapping.
We may then apply the solution given in my answer here to the domino formulation of the problem. Briefly, let $$D$$ represent a domino and let $$V$$ represent a bare vertex (one not covered by a domino). There are $$r$$ $$D$$s and $$n-2r$$ $$V$$s on our circle. The factor $$\binom{n-r}{r}$$ in your expression is the number of words one can make with these letters. Each such word may be wrapped on the circle in $$n$$ ways. But this overcounts domino configurations by a factor of $$n-r$$ since each of the $$n-r$$ cyclic permutations of the letters of a word gives rise to the same domino configurations.
Incidentally, the connection with the ménage problem is that the expression $$\frac{2n}{2n-r}\binom{2n-r}{r}$$ appears in the Touchard formula for the number of configurations: $$2\cdot n!\sum_{r=0}^n(-1)^r\frac{2n}{2n-r}\binom{2n-r}{r}(n-r)!.$$ Domino configurations have been used to enumerate unwanted configurations that need to be excluded in an inclusion-exclusion argument. See this article.