How many triangles
I saw this question today, it asks how many triangles are in this picture.
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 ?
Solution 1:
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}$$
Solution 2:
Tabulating numbers
Let $u(n,k)$ denote the number of upwards-pointing triangles of size $k$ included in a triangle of size $n$, where size is a short term for edge length. Let $d(n,k)$ likewise denote the number of down triangles. You can tabulate a few numbers to get a feeling for these. In the following table, row $n$ and column $k$ will contain two numbers separated by a comma, $u(n,k), d(n,k)$.
$$ \begin{array}{c|cccccc|c} n \backslash k & 1 & 2 & 3 & 4 & 5 & 6 & \Sigma \\\hline 1 & 1, 0 &&&&&& 1 \\ 2 & 3, 1 & 1,0 &&&&& 5 \\ 3 & 6, 3 & 3,0 & 1,0 &&&& 13 \\ 4 & 10, 6 & 6,1 & 3,0 & 1,0 &&& 27 \\ 5 & 15,10 & 10,3 & 6,0 & 3,0 & 1,0 && 48 \\ 6 & 21,15 & 15,6 & 10,1 & 6,0 & 3,0 & 1,0 & 78 \end{array} $$
Finding a pattern
Now look for patterns:
- $u(n, 1) = u(n - 1, 1) + n$ as the size change added $n$ upwards-pointing triangles
- $d(n, 1) = u(n - 1, 1)$ as the downward-pointing triangles are based on triangle grid of size one smaller
- $u(n, n) = 1$ as there is always exactly one triangle of maximal size
- $d(2k, k) = 1$ as you need at least twice its edge length to contain a downward triangle.
- $u(n, k) = u(n - 1, k - 1)$ by using the small $(k-1)$-sized triangle at the top as a representant of the larger $k$-sized triangle, excluding the bottom-most (i.e. $n$th) row.
- $d(n, k) = u(n - k, k)$ as the grid continues to expand, adding one row at a time.
Using these rules, you can extend the table above arbitrarily.
The important fact to note is that you get the same sequence of $1,3,6,10,15,21,\ldots$ over and over again, in every column. It describes grids of triangles of same size and orientation, increasing the grid size by one in each step. For this reason, those numbers are also called triangular numbers. Once you know where the first triangle appears in a given column, the number of triangles in subsequent rows is easy.
Looking up the sequence
Now take that sum column to OEIS, and you'll find this to be sequence A002717 which comes with a nice formula:
$$\left\lfloor\frac{n(n+2)(2n+1)}8\right\rfloor$$
There is also a comment stating that this sequence describes the
Number of triangles in triangular matchstick arrangement of side $n$.
Which sounds just like what you're asking.
References
If you want to know how to obtain that formula without looking it up, or how to check that formula without simply trusting an encyclopedia, then some of the references given at OEIS will likely help you out:
- J. H. Conway and R. K. Guy, The Book of Numbers, p. 83.
- F. Gerrish, How many triangles, Math. Gaz., 54 (1970), 241-246.
- J. Halsall, An interesting series, Math. Gaz., 46 (1962), 55-56.
- M. E. Larsen, The eternal triangle – a history of a counting problem, College Math. J., 20 (1989), 370-392.
- C. L. Hamberg and T. M. Green, An application of triangular numbers, Mathematics Teacher, 60 (1967), 339-342. (Referenced by Larsen)
- B. D. Mastrantone, Comment, Math. Gaz., 55 (1971), 438-440.
- Problem 889, Math. Mag., 47 (1974), 289-292.
- L. Smiley, A Quick Solution of Triangle Counting, Mathematics Magazine, 66, #1, Feb '93, p. 40.