# Number of ways to select $k$ non-adjacent vertices from polygon with $n$ vertices.

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.

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

## 2 Answers

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.)

The answer is

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

as explained in this question.