combinationscombinatoricspermutations
How many hexagons can be constructed by joining the vertices of a 15 sided polygon if none of the sides of the hexagon is also the side of the 15-gon.
My attempt
First calculate in how many ways we can select 6 points from 15 points then subtract which have 1 side same as the 15-gon then 2,3….5 sides common.
But that is very long approach .Any better method.
Consider a regular polygon with $n$ number of vertices $\mathrm{A_1, \ A_2,\ A_3, \ A_3, \ldots , A_{n-1}}$ & $\mathrm{A_{n}}$
Total number of triangles formed by joining the vertices of n-sided regular polygon $$N=\text{number of ways of selecting 3 vertices out of n}=\color{}{\binom{n}{3}}$$ $$N=\color{red}{\frac{n(n-1)(n-2)}{6}}$$ $\forall \ \ \color{blue}{n\geq 3}$
Consider a side $\mathrm{A_1A_2}$ of regular n-polygon. To get a triangle with only one side $A_1A_2$ common (As shown in figure-1 below)
(figure-1)
Join the vertices $A_1$ & $A_2$ to any of $(n-4)$ vertices i.e. $A_4, \ A_5,\ A_6, \ \ldots \ A_{n-1}$ to get triangles with only one side common. Thus there are $(n-4)$ different triangles with only one side $A_1A_2$ common. Similarly, there are $(n-4)$ different triangles with only one side $A_2A_3$ common & so on. Thus there are $(n-4)$ different triangles with each of $n$ sides common. Therefore, number of triangles $N_1$ having only one side common with that of the polygon $$N_1=\text{(No. of triangles corresponding to one side)}\text{(No. of sides)}=\color{blue}{(n-4)n}$$
(figure-2)
Now, join the alternate vertices $A_1$ & $A_3$ by a straight (blue) line to get a triangle $A_1A_2A_3$ with two sides $A_1A_2$ & $A_2A_3$ common. Similarly, join alternate vertices $A_2$ & $A_4$ to get another triangle $A_2A_3A_4$ with two sides $A_2A_3$ & $A_3A_4$ common & so on (as shown in above figure-2). Thus there are $n$ pairs of alternate & consecutive vertices to get $n$ different triangles with two sides common (Above fig-2 shows $n$ st. lines of different colors to join alternate & consecutive vertices). Therefore, number of triangles $N_2$ having two sides common with that of the polygon $$N_2=\color{blue}{n}$$ If $N_0$ is the number of triangles having no side common with that of the polygon then we have $$N=N_0+N_1+N_2$$ $$N_0=N-N_1-N_2$$ $$=\binom{n}{3}-(n-4)n-n$$ $$=\color{}{\frac{n(n-1)(n-2)}{6}-n^2+3n}$$ $$N_0=\color{red}{\frac{n(n-4)(n-5)}{6}}$$ The above formula $(N_0)$ is valid for polygon having $n$ no. of the sides such that $ \ \ \color{blue}{n\geq 6}$
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.
Best Answer
Write down $9$ $\times$'s, like this $$ \times\qquad \times\qquad \times\qquad \times\qquad \times\qquad \times\qquad \times\qquad \times\qquad \times$$
These determine $8$ gaps, plus $2$ "endgaps." We either choose $6$ gaps to put a $\circ$ into, or choose one of the two endgaps, plus $5$ real gaps to put a $\circ$ into. This can be done in $$\binom{8}{6}+2\binom{8}{5}$$ ways.
To make a real hexagon inscribed in our $15$-gon out of the pattern of $\circ$ and $\times$, take a fixed vertex of the given $15$-gon, put the leftmost of our $15$ "letters" into it, and the rest counterclockwise as we travel to the right. The $\circ$ will be the vertices of the hexagon.
The method generalizes to $k$-gons in $n$-gons.