How many triangles can be drawn all of whose vertices are vertices of a given n-gon and all of whose sides are diagonals ( not sides ) of the n-gon ?
How many k-gons can be drawn in such a way ?
[Math] Number of triangles inside given n-gon
binomial-coefficientscombinatoricsdiscrete mathematics
Related Solutions
In the case where the isosceles triangles must have vertices drawn from the regular $n$-gon, let $k$ be the number of the $n$-gon sides that are outside one of the two legs of the isosceles triangle.
For every isosceles triangle $k$ must be an even number strictly between $0$ and $n$. On the other hand, if $k$ is given, then the side lengths of the isosceles triangle also follow, and the only choice we have is which of the $n$ vertices to choose as the apex. This analysis gives $\lfloor \frac{n-1}{2}\rfloor n$ possibilities. However, if $n$ is a multiple of $3$ then we have counted each of the $n/3$ equilateral inscribed triangles tree times, and we must correct for this.
In total the number of triangles is $$ \left\lfloor \frac{n-1}{2}\right\rfloor n - \begin{cases}(2/3)n&\text{if }3|n\\0& \text{otherwise}\end{cases}$$ Or, expressed by case analysis modulo 6: $$ \#\text{isosceles} = \begin{cases} n^2/2 - (5/3) n & \text{for } n\equiv 0 \pmod 6 \\ n^2/2 - (1/2) n & \text{for } n\equiv 1, 5 \pmod 6 \\ n^2/2 - n & \text{for } n\equiv 2, 4 \pmod 6 \\ n^2/2 - (7/6) n & \text{for } n\equiv 3 \pmod 6 \end{cases}$$
The problem comes down to counting, for each $k\ge 2$, the lines intersecting an $m\times n$ grid in exactly $k$ points. (If a line contains $k$ grid points, that line contributes $\binom k3$ degenerate triangles to the count.) We will compute, for each $(m,n)$, the generating function for these lines, i.e. a polynomial in $t$ where, for $k\ge 2$, the coefficient of $t^k$ is the number of lines intersecting the grid in $k$ points. (We'll ensure we don't count any lines intersecting the grid in less than $2$ points.)
The horizontal and vertical lines contribute $n t^m$ and $m t^n$ respectively, assuming $m,n>1$. The lines of negative slope contribute the same amount as those of positive slope, so it suffices to compute the contribution from the latter. For any lattice point $(x,y)$ with $1\le x\le m$ and $1\le y\le n$, the number of grid points on the ray with slope $p/q$ ending at $(x,y)$ is $$\min(\lceil\frac xp\rceil,\lceil\frac yq\rceil).$$ Note that in order for that segment to have at least two gridpoints we would need to have $x>p$ and $y>q$. So, if we set $$f(m,n,p,q;t)=\sum_{x=p+1}^m\sum_{y=q+1}^n t^{\min(\lceil x/p\rceil,\lceil y/q\rceil},$$ then $f(m,n,p,q;t)-f(m-p,n-q,p,q;t)$ is the generating function for lines of slope $p/q$ according to the number of grid points they contain.
To get the generating function for all lines, we sum over relatively prime pairs $p$ and $q$, with $1\le p\le m$ and $1\le q\le n$, double the result, and add the contributions for horizontal and vertical lines:
$$g(m,n;t)=n t^m [m>1] + m t^n [n>1] + 2\sum_{\substack{p,q\\(p,q)=1}} f(m,n,p,q;t)-f(m-p,n-q,p,q;t).$$
To check the answer, and hopefully find references, we compute this for small values with $m=n$ (i.e. for square grids), evaluate at $t=1$ (which forgets the length information) and hope that the result shows up in the Sloane OEIS. We get:
$$\begin{array}{ccc} n & g(n,n;t) & g(n,n;1)\\ \hline 1 & 0 & 0\\ 2 & 6 t^2 & 6\\ 3 & 8 t^3+12 t^2 & 20\\ 4 & 10 t^4+4 t^3+48 t^2 & 62\\ 5 & 12 t^5+4 t^4+16 t^3+108 t^2 & 140 \\ 6 & 14 t^6+4 t^5+4 t^4+36 t^3+248 t^2 & 306 \\ 7 & 16 t^7+4 t^6+4 t^5+20 t^4+64 t^3+428 t^2 & 536\\ \end{array} $$
We're in luck! The sequence appears in OEIS as A018808, which includes some promising references. I note that the formulas given there have the form of summations (although with slightly lower complexity than the ones I've written down), so it's unlikely you'll get a closed form.
For completeness, the number of degenerate triples corresponding to the rows of the table are $0, 0, 8, 44, 152, 372, 824$; these are obtained by replacing $t^k$ by $\binom k3$.
Best Answer
This is the same as asking how many ways $k$ vertices can be chosen from the $n$-gon such that no two of the chosen vertices are neighbors. If we select one of the $n$ vertices to be the "first" one and write them down in order $$ 1 ~~ 2 ~~ 3 ~~ \cdots ~~ n $$ we must choose $k$ of these numbers such that no neighbors are chosen and such that $1$ and $n$ are not both chosen.
It is convenient to split into two cases: those where vertex $1$ is not among the chosen vertices, and those where it is chosen.
If vertex $1$ is not chosen, we just need to fill out the distribute $k$ blocks of the shape "no yes" and $n-2k$ blocks of the shape "no" into the linear array. There are $\binom{n-k}{k}$ ways to do this.
If vertex $1$ is chosen, then effectively there's a "no yes" block straddling the positions $n$ and $1$. The remaining blocks can be placed in $\binom{n-k-1}{k-1}$ ways.
So the total number of possibilities is $\binom{n-k}{k}+\binom{n-k-1}{k-1}$.