How Many Triangles?

In a previous post, How many squares are there on a chess board?, I closed with the following challenge:

How many triangles (of all sizes) do you see in the equilateral triangle below?

A lot of people attempted a solution, and a few got it right, but this puzzle proved a bit more challenging than counting the squares on a chessboard so it's time to give the full solution. It might seem like a simple task of counting up the triangles, but it's even harder to keep track of which triangles you've already counted than it was with squares. In addition to that, I'm always much more interested in a general approach to a puzzle than I am in the solution to a specific instance of the puzzle.

Before we begin, let's get a bit of terminology out of the way. I'll be referring to each specific instance of this problem by the number of unit-triangles at its base. The unit-triangle is the smallest triangle in each image, and the base is the number of unit-triangles along the bottom edge. In the image above, there are five unit-triangles in the base. Let's call the number of unit-triangles in an image u(n), where n is the number of unit-triangles in the base, and the total number of triangles in an image T(n).

Starting at the beginning, we see that the simplest case consists of only one triangle.

u(1) = 1
T(1) = 1

Next we have a triangle that has two triangles at its base. Counting the unit-triangles we get four, plus the larger triangle they form, for a total of five.

u(2) = 4
T(2) = 5

Next we move up to a base-3 triangle. You can see from the image below that it's made up of 9 units.

u(3) = 9

In addition, there are three base-2 triangles (one in each corner, see images below), plus the base-3 triangle itself, for a total of 13.

T(3) = 13

At this point you should note that any base-n triangle consists of three base-(n-1) triangles, one for each corner. The only exception to this rule is at base-2, which we saw consists of four base-1 triangles, one for each corner and one in the middle. From here on, I won't illustrate the three corner base-(n-1) triangles.

A triangle with a base of four units consists of itself, 16 units, seven base-2 triangles, and the three base-3 triangles in each corner, for a total of 27.

u(4) = 16
T(4) = 27

I won't illustrate all seven of the base-2 triangles, but many people do miscount them, so I'll list them by their numbered units to help you visualize them.

{ 1, 2, 3, 4 }
{ 2, 5, 6, 7 }
{ 4, 7, 8, 9 }
{ 5, 10, 11, 12 }
{ 7, 12, 13, 14 }
{ 9, 14, 15, 16 }
{ 6, 7, 8, 13 }

Note that the last triangle listed, { 6, 7, 8, 13 }, is a downward-pointing triangle. This is important because there are more of these as you increase the size of the base, and because many people overlook them while counting. Make sure that you can see all the triangles listed before continuing on.

Finally, we come to the base-5 triangle that we set out to solve at the beginning. It's made up of 25 units, 13 base-2 triangles, six base-3 triangles, three base-4 triangles in the corners, and itself for a total of 48 triangles.

u(5) = 25
T(5) = 48

I won't go through and illustrate all 48 of them, but hopefully the visual cues I provided in the previous illustrations help you to arrive at the same count that I did.

A General Formula

Now that we have the solutions to several small instances of the triangle problem, we have enough information to search for a general formula. Other than the fact that for each instance the number of unit-triangles is the square of the base, I don't see any interesting patterns in the sequence, so I'll skip directly to searching for one. Searching for the sequence 1, 5, 13, 27, 48 in the Online Encyclopedia of Integer Sequences leads me to this resource.

The comments identify this problem as

Number of triangles in triangular matchstick arrangement of side n.

which is a very general way of stating the original problem (where the problem was originally posed by laying out matchsticks on a table, rather than drawing triangles in an image editor).

The formula given for the sequence is:

T(n) = floor(n * (n + 2) * (2n + 1) / 8)

I could stop there, but I want to explain what the floor function is, and why it's needed in this case. The floor function in mathematics simply gives the largest integer less than or equal to its input. It simply rounds down to the nearest whole number (unless the input is already a whole number, in which case the output is exactly the same whole number as the input).

To see why we need to floor the results of this calculation, consider two things. First, when we're counting the triangles in the original image, I hope it's apparent that we will always come up with a whole number of triangles. That is, we'll never have some fractional part of a triangle left over. The answer will always be an integer value. Second, if we look at the results of the formula without using the floor function, we can see that it is needed.

f(n) = n * (n + 2) * (2n + 1) / 8
f(1) = 1 * (1 + 2) * (2*1 + 1) / 8 = 1.125
f(2) = 2 * (2 + 2) * (2*2 + 1) / 8 = 5.000
f(3) = 3 * (3 + 2) * (2*3 + 1) / 8 = 13.125
f(4) = 4 * (4 + 2) * (2*4 + 1) / 8 = 27.000
f(5) = 5 * (5 + 2) * (2*5 + 1) / 8 = 48.125

Note that when n is odd, there is always some a fractional remainder left over from applying the formula. Flooring the result removes this residue, giving us the same whole number answer we would arrive at by counting.

Since the remainder is always exactly equal to 1/8, we could get the same result by using two different formulas, one for even inputs, and one for odd inputs. This is the approach taken with the formulas given on on Wolfram MathWorld's Triangle Tiling article.


In Closing...

Congratulations to everyone who took the time to work through the solution to this problem. I'd like to thank everyone who left a comment on the original post. Your questions and comments made that one of the most fun (for me) posts I've written so far. I hope you enjoyed it as much as I did.