3
$\begingroup$

I am looking for the number of ways to select $k$ non-adjacent vertices from an $n$-gon.

Since different rotations are considered different selections I can not use the Burnside Lemma, and the problem is the same as selecting $k$ non-consecutive numbers from $\{1,2,...,n\}$ when we consider $1$ and $n$ to be consecutive.

I know how to find the number of all subsets of $\{1,2,...,n\}$ that do not contain consecutive numbers, but I don't know how to get the number of subsets that contain exactly $k$ elements.

$\endgroup$
  • $\begingroup$ isn't an n-gon just a cycle with n vertices? $\endgroup$ – Sentinel135 Feb 27 '17 at 7:51
  • $\begingroup$ Yes it is, but how does this help me? $\endgroup$ – Felix Auer Feb 27 '17 at 8:03
4
$\begingroup$

Let's count the number of admissible choices with one chosen vertex colored red.

We can chose the red vertex in $n$ ways. For the remaining choices write an arbitrary bit string of length $n-1-k$ containing exactly $k-1$ ones. There are ${n-1-k\choose k-1}$ such strings. Prepend a zero, and insert a zero after each $1$ in the written string. The string now has length $n-1$ and contains $k-1$ ones, none at the start and no two of them consecutive. This enlarged string encodes the selection of the remaining $k-1$ vertices.

Since in reality there is no distinguished selected vertex we have to divide by $k$ in order to arrive at the final number $$N={n\over k}\>{n-1-k\choose k-1}\ .$$ (This coincides with Felx Auer's quote.)

$\endgroup$
1
$\begingroup$

The answer is

$ \dbinom{n-k+1}{k}-\dbinom{n-k-1}{k-2}$

as explained in this question.

$\endgroup$

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.