1

Find the number of polygons that can be formed, none of whose sides coincide with those of the n-sided polygon.

Since we have to form an r sided polygon, it is obvious that we would have to select r vertices from the n vertices of the n-sided polygon the restriction being, that no consecutive vertices should be chosen. So to ensure that these vertices are separated we can select $n-r \choose r$ vertices that are between the selected vertices as separators.
This is where I got stuck. I tried searching the web but couldn't find any satisfactory explanations. Could someone please help me out with the logical approach to solve this?

Prajwal Tiwari
  • 457
  • Essentially a duplicate of https://math.stackexchange.com/q/1663877/. They just do $r=7$, but the same logic applies to any $r$. – Mike Earnest Feb 22 '21 at 15:16

1 Answers1

4

Assuming you start with a convex polygon and you want to select convex polygons, you have to select $r$ vertices from $n$ where $ r \ge 3$ and you do not select adjacent vertices.

Suppose one of the vertices is $A$. Then you want $r-1$ non-adjacent vertices from the $n-3$ vertices which are not $A$ or its neighbours.

You could use induction or a form of stars and bars to show this is ${n - r-1 \choose r-1}$

But you need to multiply this by $n$ as the number of choices for $A$, and divide by $r$ as each polygon is counted multiple times, suggesting the answer may be $$\frac nr{n - r-1 \choose r-1} $$ at least when $r \ge 3$. As a check, this give the obvious answer of $2$ when $n=2r$.

Henry
  • 157,058
  • could you please elaborate on how we can get the number of vertices from which we have to select r-1 equals to n-r-1 ? – Prajwal Tiwari Feb 22 '21 at 11:37
  • @PrajwalTiwari You have to select from $n-3$ vertices subject to the constraint that the $r-1$ selections are non-adjacent vertices: that reduces the number of possibilities. If you had been selecting $k$ non-adjacent vertices from $m$ there would have been ${m-k+1 \choose k}$ possibilities – Henry Feb 22 '21 at 11:46