How many triangles can be formed from the vertices of a polygon of $n$ sides if the triangle and the polygon may not share sides?

Question

Note: not a duplicate of this question as I'd like to know what's wrong with my approach.

My attempt: Choose any 3 of the $n$ vertices of the polygon, and let the number of points between the three be $x$,$y$ and $z$. Then, $x+y+z=n-3$ and $x, y, z\ge 1$. The number of possible solutions is a sticks-and-stars problem, and can be shown to be $n-4 \choose 2$. From the top answer to the question linked above though, the correct answer is $\binom{n}{3}-(n-4)n-n$.

Putting in some values for $n$, I can see that I'm undercounting. How?

Answer 1

Your approach is nearly correct, you just need to tweak it because you are only determining the spacing between the vertices, but not the vertices concretely.

For instance, if $n=10$, then the solution $3 + 2 + 3$ means you picked 3 vertices spaced out by $3,2$ and $3$, but concretely we don't know which they are. (You basically need to pick one of the vertices, because then the others will be fixed.)

In fact, if you multiply your result by $n/3$, you'll see that you get the correct result:

$$\frac n3\binom{n-4}2 = \frac{n(n-4)(n-5)}{6} = \binom n3-(n-4)n-n.$$

Answer 2

1. How are you setting up the bijection?

IE Say $n = 10$ and we chose vertices 2, 4, 6. What does $x, y, z$ correspond to?

---

What you're going for is something along the lines of

• Fix a vertex of the triangle, let it be vertex 1. There are $n$ possibilities.
• Let $x \geq 2 $ correspond to the difference between the index of the second vertex and vertex 1.
• Let $y \geq 2$ correspond to the difference in the index of the third and second vertex.
• Let $z \geq 1$ correspond to the difference between $n$ and the index of the third vertex
• We have $x+y+z = n-1$ and $(x-1) + (y-1) + z = n-3$ as positive integer solutions. Thus, there are ${n-4 \choose 2 }$ possibilities.

Hence, there are $ n \times { n - 4 \choose 2 } $ possibilities, but we double-counted 3 times, so it is $ \frac{ n (n-4)(n-5) } { 6}$.