How many triangles

I saw this question today, it asks how many triangles are in this picture.

enter image description here

I don’t know how to solve this (without counting directly), though I guess it has something to do with some recurrence.

How can count the number of all triangles in the picture ?

Answer

Say that instead of four triangles along each edge we have $n$. First count the triangles that point up. This is easy to do if you count them by top vertex. Each vertex in the picture is the top of one triangle for every horizontal grid line below it. Thus, the topmost vertex, which has $n$ horizontal gridlines below it, is the top vertex of $n$ triangles; each of the two vertices in the next row down is the top vertex of $n-1$ triangles; and so on. This gives us a total of

$$\begin{align*}
\sum_{k=1}^nk(n+1-k)&=\frac12n(n+1)^2-\sum_{k=1}^nk^2\\
&=\frac12n(n+1)^2-\frac16n(n+1)(2n+1)\\
&=\frac16n(n+1)\Big(3(n+1)-(2n+1)\Big)\\
&=\frac16n(n+1)(n+2)\\
&=\binom{n+2}3
\end{align*}$$

upward-pointing triangles.

The downward-pointing triangles can be counted by their by their bottom vertices, but it’s a bit messier. First, each vertex not on the left or right edge of the figure is the bottom vertex of a triangle of height $1$, and there are $$\sum_{k=1}^{n-1}=\binom{n}2$$ of them. Each vertex that is not on the left or right edge or on the slant grid lines adjacent to those edges is the bottom vertex of a triangle of height $2$, and there are

$$\sum_{k=1}^{n-3}k=\binom{n-2}2$$ of them. In general each vertex that is not on the left or right edge or on one of the $h-1$ slant grid lines nearest each of those edges is the bottom vertex of a triangle of height $h$, and there are

$$\sum_{k=1}^{n+1-2h}k=\binom{n+2-2h}2$$ of them.

Algebra beyond this point corrected.

The total number of downward-pointing triangles is therefore

$$\begin{align*}
\sum_{h\ge 1}\binom{n+2-2h}2&=\sum_{k=0}^{\lfloor n/2\rfloor-1}\binom{n-2k}2\\
&=\frac12\sum_{k=0}^{\lfloor n/2\rfloor-1}(n-2k)(n-2k-1)\\
&=\frac12\sum_{k=0}^{\lfloor n/2\rfloor-1}\left(n^2-4kn+4k^2-n+2k\right)\\
&=\left\lfloor\frac{n}2\right\rfloor\binom{n}2+2\sum_{k=0}^{\lfloor n/2\rfloor-1}k^2-(2n-1)\sum_{k=0}^{\lfloor n/2\rfloor-1}k\\
&=\left\lfloor\frac{n}2\right\rfloor\binom{n}2+\frac13\left\lfloor\frac{n}2\right\rfloor\left(\left\lfloor\frac{n}2\right\rfloor-1\right)\left(2\left\lfloor\frac{n}2\right\rfloor-1\right)\\
&\qquad\qquad-\frac12(2n-1)\left\lfloor\frac{n}2\right\rfloor\left(\left\lfloor\frac{n}2\right\rfloor-1\right)\;.
\end{align*}$$

Set $\displaystyle m=\left\lfloor\frac{n}2\right\rfloor$, and this becomes

$$\begin{align*}
&m\binom{n}2+\frac13m(m-1)(2m-1)-\frac12(2n-1)m(m-1)\\
&\qquad\qquad=m\binom{n}2+m(m-1)\left(\frac{2m-1}3-n+\frac12\right)\;.
\end{align*}$$

This simplifies to $$\frac1{24}n(n+2)(2n-1)$$ for even $n$ and to

$$\frac1{24}\left(n^2-1\right)(2n+3)$$ for odd $n$.

The final figure, then is

$$\binom{n+2}3+\begin{cases}
\frac1{24}n(n+2)(2n-1),&\text{if }n\text{ is even}\\\\
\frac1{24}\left(n^2-1\right)(2n+3),&\text{if }n\text{ is odd}\;.
\end{cases}$$

Attribution
Source : Link , Question Author : Belgi , Answer Author : Brian M. Scott

Leave a Comment