Polygons within a polygon

Question

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

Answer 1

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.

Answer 2

Your problem is equivalent to finding the number of unordered subsets of $\{1, 2, ..., n\}$ such that in each subset $\{v_1, v_2, ..., v_r\}$, $v_i-v_{i-1} \not \in \{1, n-1\}$ for any $i\ge1$. Let $a_{r,n}$ be this number.

Now, let the linear case be finding the number of unordered subsets of $\{1, 2, ..., n\}$ such that in each subset $\{v_1, v_2, ..., v_r\}$, $v_i-v_{i-1} \not = 1$ for any $i\ge1$. Let $b_{r, n}$ be this number. $b_{r,n}$ is given by the following recursive sum: $$b_{r,n}=\underbrace{b_{r-1,0}}_{\text{choosing vertex }1}+\sum_{i=0}^{n-2}\underbrace{b_{r-1, i}}_{\text{vertex }i+2}$$

where $b_{r,n}=0$ if $r > n$, $b_{0, n}=1$, and $b_{1, n} = n$. Using $b_{r,n}$, $a_{r,n}$ can be found as

$$a_{r,n} = \underbrace{b_{r-1,0}}_{\text{vertex }1}+\sum_{i=0}^{n-3} \underbrace{b_{r-1, i}}_{\text{vertex }i+2}+\underbrace{b_{r-1,n-3}}_{\text{choosing vertex }n}$$

Basically, every step, you are choosing a vertex and "eliminating" the ones after that and neighboring ones. Just like $b_{r,n}$, $a_{r,n}=0$ if $r > n$, $1$ if $r = 0$, and $n$ if $r = 1$.

$b_{r, n}$ has a very simple closed-form of $$\binom{n-r+1}{r}$$ which can be proven inductively using Pascal's identity. This then means that $$a_{r,n} = \binom{n-r-1}{r-1}+\sum_{i=r-1}^{n-r-1}\binom{i}{r-1}$$ for $r < n$. This simplifies to $$a_{r,n}= \frac{n}{n-r}\binom{n-r}{r}$$ for $r < n$. This can be proven by induction on $n$ after using the fact that $a_{r,n+1}-a_{r,n}$ must equal $$2\binom{n-r}{r-1}- \binom{n-r-1}{r-1}$$ and $a_{r,2r}=2$.