$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?
Best Answer
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.