0
$\begingroup$

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?

$\endgroup$
1
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$ Feb 22 at 11:37
  • $\begingroup$ @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 $\endgroup$
    – Henry
    Feb 22 at 11:46

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.