0
$\begingroup$

$r$-sided polygons are formed by joining the vertices of a $n$-sided polygon.Find the number of polygons that can be formed,none of whose sides coincide with those of the $n$-sided polygon?

Polygon is convex.

In think we need to count here the number of polygons with one side common with $n$-sided polygon, up to $r-1$ sides common with original polygon and then subtract with total number of polygons, but how to do this counting?

$\endgroup$
1
$\begingroup$

First, we consider the following question:

There are $n$ vertices in a line (first and last not connected) and we want to pick at least $3$ disjoint vertices. Let this number be $f(n)$, then $f(5)=1,f(6)=4$ .etc.

In general, $f(n)=f(n-1)+f(n-2)+{n-2\choose2}-(n-3)=f(n-1)+f(n-2)+{(n-2)(n-3)\over2}-(n-3)=f(n-1)+f(n-2)+{(n-4)(n-3)\over2}$ by separating "including first vertex" case and "excluding" case and "including with only two other vertex" case.

Now define $g(n)$ to be your number (i.e. n vertices in a cyclic way now instead of a line) and then we have

$g(n)=f(n)-f(n-2)-(n-4)-({n-4\choose2}-(n-5))=f(n-1)+{(n-4)(n-3)\over2}-{(n-4)(n-5)\over2}-1=f(n-1)+(n-5)$

by excluding the cases where both first and last are chosen.

Now if you can solve $f$ you can find $g$ as well.

$\endgroup$
  • $\begingroup$ Can you please elaborate a bit more? $\endgroup$ – Mathematics Nov 27 '15 at 11:22
  • $\begingroup$ Which part do you not understand? For the $f(n)$ part, if we include the first vertex then we cannot have second chosen so it is $f(n-2)$ and if we exclude the first vertex it is $f(n-1)$. However $f(n-2)$ only counts the case where 3 or more vertices are chosen so it only counts $4$ or more vertices for $f(n)$ and we need to include cases for "first chosen and two other vertices chosen" case, which has ${n-2\choose2}-(n-3)$ ways of choosing. $\endgroup$ – cr001 Nov 27 '15 at 15:46
  • $\begingroup$ For the $g(n)$ part, we use $f(n)$ but add the extra rule that the first and last cannot be chosen simultaneously so we minus out the cases where both are chosen. When both are chosen we have $f(n-2)$ but that's not all, we still need to count the cases where one other vertex is chosen(so totally 3) and the cases where two other vertex is chosen(so totally 4). Totally $5$ or more cases are covered by $f(n-2)$. $\endgroup$ – cr001 Nov 27 '15 at 15:48

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.