Number of triangles inside given n-gon?

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 ?

• See this for a slightly related problem. – Henning Makholm Sep 3 '12 at 14:11

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}$.

• +1 A much better answer than my hints. I'd write $\binom{n-2-(k-1)}{k-1}=\binom{n-k-1}{k-1}$ the first time, to make it clearer where this comes from, but really very nice! – Marc van Leeuwen Sep 3 '12 at 14:17
• @MarcvanLeeuwen: Thanks. Actually for me it came directly from subtracting $1$ at each floor of $\binom{n-k}{k}$ (since one of the blocks is now out of the game), but whatever works for you ... – Henning Makholm Sep 3 '12 at 14:26
• I reasoned that one of the blocks was out of the game and two of the spaces in the array. Did you arrive at subtracting $1$ from the top floor without using $2-1=1$? OK, I see you read the top index as the total number of blocks, rather than as $n-k$. Fine! – Marc van Leeuwen Sep 3 '12 at 14:29
• @Marc: Yes -- there used to be $n-k$ blocks in total; with one of them out of the game there's simply one less than that. (I trust their lengths to add up to $n-2$ without any help from me, because they used to sum to $n$ and I have removed one block of length $2$). – Henning Makholm Sep 3 '12 at 14:33

First we look at a problem that has cropped up several times on this site, for example here. How many ways can we line up $k$ identical children and $n-k$ identical adults so that no two children are next to each other?

Line up the adults, with some space between them. The $n-k$ adults determine $n-k+1$ gaps (there is a "gap" at each end). We must choose $k$ of these gaps to put a child into. This can be done in $$\binom{n-k+1}{k}$$ ways. Now we look at the closely related problem of seating the people in chairs around a circular table, so that no two children are next to each other. (The chairs are numbered, so they are to be considered distinct.)

The answer for the line is almost right. The only problem is that the situations in which there are children at both ends of the line (and therefore adults next to them) is now forbidden.

How many such bad configurations are there? We now have to place $k-2$ children and $n-k-2$ adults so that no two children are next to each other. By the same reasoning as the one we used above, this can be done in $\binom{n-k-1}{k-2}$ ways. Thus for the circle the total number of ways is $$\binom{n-k+1}{k}-\binom{n-k-1}{k-2}.$$ This is the number of $k$-gons of the type described in the question.

• And note that since $$\binom{n-k+1}k=\binom{n-k}k+\binom{n-k}{k-1} =\binom{n-k}k+\binom{n-k-1}{k-1}+\binom{n-k-1}{k-2}$$ this result agrees with that of Henning Makholm – Marc van Leeuwen Sep 3 '12 at 15:48