Problem Post 3-1: How many Shapes, Part 4: Triangles

		Problem Posts
		Part 4 of 4 in How Many Shapes?

[Level 3]

So last time we finished off the dreary onus of counting rectangles in rectangles. Now for something completely different.

CAN WE DO BETTER?

• What if the original grid were a rectangle, instead of a square? Or an irregular figure?
• What if we were counting rectangles instead of squares?
• What if some of the grid 'wires' are missing?
• What if we're working on a triangular grid, counting triangles? Does our logic still apply?

3 Triangles!

This one was surprising to say the least. I had hoped to find a straightforward formula like in counting rectangles, but it turns out triangle counting is nastier than one might think!

QUESTION
Find a simple formula to count $a_n$, the number of triangles you can find in a big triangular grid of size $n$.

There are several ways to categorize and count. Here's one solving the problem for $n=5$:

What we're doing here is counting the size 1 triangles first (right side up and upside down), then proceeding to do the same for size 2, 3, 4, and 5 triangles.


And here's another, looking for the total number of size 2 triangles for $n=6$:

This time, we use a somewhat systematic way of counting the size 2 triangles: we look at where the base (biggest row at the bottom when it's right side up) of each triangle resides. It may be a bit tricky to get at first, but a few re-views should make it clear.

To generalize, let's choose the method in the second GIF.

NOTE
I've formulated solutions that involve the method in the first GIF, which has the added advantage of seeing the triangular numbers figuring in. I've chosen to do the second method because I feel it is more expedient, and also the less popular option.

So the second GIF shows us how many size 2 triangles there are for $n=6$. It does this by counting how many of these size 2 triangles have their bases in Row 1, how many in Row 2, and so on. We can do this to triangles of all sizes to get a total.

Given the size of the little triangle, there's a subtle pattern to the number of these based on a particular row. It switches where we begin to have nonexistent upside-down triangles. To see this pattern, let's organize the information into a useful table. (For example, there are two Size 4 triangles that have their bases on Row 5. In particular, notice the row of Size 2 gives us 0, 1, 3, 5, 7, 5, the numbers in the GIF.)

	Row 1	Row 2	Row 3	Row 4	Row 5	Row 6	Subtotal
Size 1	1	3	5	7	9	11	36
Size 2	0	1	3	5	7	5	21
Size 3	0	0	1	3	3	4	11
Size 4	0	0	0	1	2	3	6
Size 5	0	0	0	0	1	2	3
Size 6	0	0	0	0	0	1	1
Total	78

Now when we work with these odd/even patterns extensively, we have to suspect whether or not the table will be the same regardless of the parity of the size of our big triangle. To check, let's do the table for a size 11 big triangle: 

	1	2	3	4	5	6	7	8	9	10	11	Subtotal
1	1	3	5	7	9	11	13	15	17	19	21	121
2	0	1	3	5	7	9	11	13	15	17	10	91
3	0	0	1	3	5	7	9	11	13	8	9	66
4	0	0	0	1	3	5	7	9	6	7	8	46
5	0	0	0	0	1	3	5	4	5	6	7	31
6	0	0	0	0	0	1	2	3	4	5	6	21
7	0	0	0	0	0	0	1	2	3	4	5	15
8	0	0	0	0	0	0	0	1	2	3	4	10
9	0	0	0	0	0	0	0	0	1	2	3	6
10	0	0	0	0	0	0	0	0	0	1	2	3
11	0	0	0	0	0	0	0	0	0	0	1	1
Total												411

It's become clear that the tables are not entirely analogous, so we have to split for the odd and even cases. 

Odd Case

Summing the red entries row-wise and the black entries column-wise:\begin{eqnarray*} a_{11} & = & \left(1+3+\cdots+21\right)+\cdots+\left(1\right)\\  &  & +\left(1+2\right)+\left(1+2+3\right)+\cdots+\left(1+\cdots+10\right)\\  & = & 1^{2}+3^{2}+\cdots+11^{2}\\  &  & +\frac{1}{2}\left(2\cdot3+4\cdot5+\cdots+10\cdot11\right)\\  & = & \left(1^{2}+2^{2}+\cdots+11^{2}\right)-\left(2^{2}+4^{2}+\cdots+10^{2}\right)\\  &  & +\frac{1}{2}\left(2^{2}+\cdots+10^{2}\right)+\frac{1}{2}\left(2+4+\cdots+10\right)\\  & = & \frac{11\cdot12\cdot23}{6}-4\frac{5\cdot6\cdot11}{6}\\  &  & +2\frac{5\cdot6\cdot11}{6}+\frac{5\cdot6}{2}\\  & = & \frac{11\cdot12\cdot23}{6}-2\frac{5\cdot6\cdot11}{6}+\frac{5\cdot6}{2}\\  & = & \boxed{411} \end{eqnarray*}

Now if we had an arbitrary odd $n$, it follows that the penultimate expression becomes
\begin{eqnarray*} a_{n} & = & \frac{n\left(n+1\right)\left(2n+1\right)}{6}-2\frac{n\left(n-1\right)\left(n+1\right)}{24}+\frac{\left(n-1\right)\left(n+1\right)}{8}\\  & = & \frac{\left(2n^{2}+3n-1\right)\left(n+1\right)}{8} \end{eqnarray*}

Even Case

Again we sum red entries horizontally and even entries vertically:
\begin{eqnarray*} a_{6} & = & \left(1+3+\cdots+11\right)+\cdots+\left(1+3\right)\\  &  & +\left(1\right)+\left(1+2+3\right)+\cdots+\left(1+2+\cdots+5\right)\\  & = & 2^{2}+4^{2}+6^{2}\\  &  & +\frac{1}{2}\left(1\cdot2+3\cdot4+5\cdot6\right)\\  & = & \left(2^{2}+4^{2}+6^{2}\right)\\  &  & +\frac{1}{2}\left(2^{2}+4^{2}+6^{2}\right)-\frac{1}{2}\left(2\cdot4\cdot6\right)\\  & = & 6\frac{3\cdot4\cdot7}{6}-\frac{3\cdot4}{2}\\  & = & \boxed{78} \end{eqnarray*}

Now for arbitrary even $n$ the penultimate expression becomes \begin{eqnarray*} a_{n} & = & \frac{n\left(n+2\right)\left(2n+2\right)}{8}-\frac{n\left(n+2\right)}{8}\\  & = & \frac{n\left(n+2\right)\left(2n+1\right)}{8} \end{eqnarray*}

So finally we have \[ a_{n}=\begin{cases} \dfrac{n\left(n+2\right)\left(2n+1\right)}{8} & \text{if }n\text{ is even}\\ \dfrac{\left(2n^{2}+3n-1\right)\left(n+1\right)}{8} & \text{otherwise} \end{cases} \]

Or, presented in a more revealing form: \[ a_{n}=\begin{cases} \dfrac{2n^{3}+5n^{2}+2n}{8} & \text{if }n\text{ is even}\\ \dfrac{2n^{3}+5n^{2}+2n-1}{8} & \text{otherwise} \end{cases} \]

Now we're sure that if $n$ is odd, $a_{n}=\frac{2n^{3}+5n^{2}+2n-1}{8}$ must be an integer, meaning $\frac{2n^{3}+5n^{2}+2n}{8}$ is only $a_{n}$ plus $\frac{1}{8}$. Since the formula for even $n$ is so much nicer, why don't we just do that all the time and round down to the nearest integer?

SOLUTION
The number of triangles of all sizes in a triangular size $n$ grid is\[ a_{n}=\left\lfloor \frac{n\left(n+2\right)\left(2n+1\right)}{8}\right\rfloor \]

(Note how this is of a strikingly similar form as the formulae we derived in Problem Post 1-7). And there we have it! A slick, simple formula.

As for missing gridlines, irregular triangular grids, and other whatnot, the same strategies as in rectangle counting apply.