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.

  • $\begingroup$ 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$. $\endgroup$ Nov 11 '17 at 19:30
  • 2
    $\begingroup$ Why would placing the objects on a circle affect the number of ways of selecting the objects? $\endgroup$
    – Jens
    Nov 12 '17 at 0:00
  • $\begingroup$ Your formulas do not make sense. Please check the wording of the question. $\endgroup$ Nov 12 '17 at 10:23
  • $\begingroup$ You are right. I am editing. $\endgroup$
    – Maverick
    Nov 12 '17 at 11:29
  • $\begingroup$ 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}$$ $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.