Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
There are n sides of a polygon(where $n>5$).
Triangles are formed by joining the vertices of the polygon. How many triangles can be constructed with no side common to the polygon?
My try:
Total possible triangles = $\frac{(n)(n-1)(n-2)}{6} = \binom{n}{3}$ ------(1)
Triangles with 2 sides common = $n$ ------(2)
Triangles with 1 side common = $n(n-4)$ ------(3)
So, with no side common = $1-2-3$
Is there any other way to get it directly without following this process?
We count the number of "good" triangles with one vertex painted blue.
The blue vertex can be chosen in $n$ ways. For every one of these ways, the two neighbouring vertices are forbidden. That leaves $n-3$ vertices. Write down $n-5$ stars, with a little space between them, like this: $$\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast\qquad\ast$$ That determines $n-4$ "gaps" ($n-5$ ordinary gaps, plus $2$ endgaps) to slip our $2$ remaining vertices into.
There are $\binom{n-4}{2}$ ways to choose these gaps. So there is a total of $n\binom{n-4}{2}$ good triangles with a blue vertex.
This counts each uncoloured good triangle $3$ times. So the number of these is $\frac{1}{3}\cdot n\binom{n-4}{2}$.
Note that the idea generalizes to good (convex) quadrilaterals, and so on.
First let us find the number of solutions to $$d_1+d_2+d_3=n$$ such that $d_i\geq 2$. This is same as the number of solutions in positive integers to $$d_1+d_2+d_3=n-3$$ By stars and bars method this is $\binom{n-4}{2}$. For each such solution, we have $n$ possible triangles and each triangle is counted three times. Thus the number of triangles is $\frac{n}{3}\binom{n-4}{2}$
Suppose you choose a corner of the polygon(n possibilities). Then for the next vertex, you can choose any vertex that is not within one unit of the first vertex (n-3 possibilities). Then proceed with casework:
Case 1: The second vertex is within 2 units of the first vertex. (2 possibilities) Then there are 5 points you cannot choose for the the next vertex. So the total from this case is $n(2)(n-5)=2n^2-10n$
Case 2: any other vertex. The total from this case is $n(n-3-2)(n-6)=n^3-11n^2+30n.$ Therefore the total is $n^3-9n^2+20n=n(n-4)(n-5)$.
Looking clockwise, attach one unused vertex $\Large\bullet$ to each of the $3$ used vertices $\Large\circ$ that will form the triangle, viz. $\boxed{\Large{\circ\bullet}}$
Now there are $3$ boxes + $(n-6) = (n-3)$ objects.
Place the boxes in $\binom{n-3}{3}$ ways,
but you are allowing objects only $(n-3)$ places instead of $n$, so multiply by $\frac{n}{n-3}$ to get
formula $=\frac{n}{n-3}\times\binom{n-3}{3}$
