This is the solution to a problem I posed in my previous blog post. Please read that post first.
[Update: I posted a solution to this problem two days ago. Yesterday Brent Yorgey pointed out that my analysis of “type 2″ triangles was not quite correct. (See his comment below.) So I went back to the whiteboard and worked out the correct solution. Hopefully the formula given below is correct. Thanks, Brent!]
Here’s a recap of the problem: How many triangles are there in an grid of squares with X’s through them (as shown below)?
We realized that there are two types of triangles. We’ll say a triangle is of “type 1″ if the legs of the triangle run horizontally and vertically (as shown below).
A triangle is of “type 2″ if the hypotenuse runs either horizontally or vertically (as shown below).
Consider the type 1 triangles with horizontal (or vertical) segments in each leg. Examples of are shown in the diagram. When there are such triangles in the ceiling. In particular, there are having the orientation shown, but then they can be rotated 90, 180, or 270 degrees. When there are such triangles. When there are , etc. Thus, the total number of type 1 triangles is
Counting the type 2 triangles is tricker. Let denote the number of segments in the hypotenuse of the triangle. Examples of are shown in the diagram. The key observation is that each time increases by one unit the horizontal distance (in the given configuration) increases by a half unit.
For example, when here are the number of type 2 triangles of a given orientation for the possible values of (so the final count will be four times the sum of these).
And here are the number when .
In general, for a given and and a given orientation we can fit triangles in one direction and in the other. Thus the number of type 2 triangles is
It follows that there is a different closed form for this summation for even and odd.
Consider the case that is even. I’ll skip most of the algebraic details, but essentially I summed the values for even and odd separately.
Now suppose is odd.
Adding the number of type 1 and type 2 triangles and simplifying the expression we find that the total number of triangles in an grid is
when is even and
when is odd.
Thus, here are the number of triangles for the first few -values:
In particular, there are 268 triangles in the example at the start of the blog post.
When I posted my first solution I claimed that this sequence was not in the On-line Encyclopedia of Integer Sequences database. Now that I’ve corrected the formula (and hence the fourth term of the sequence), I discovered that it is already there!. (They give more terms of sequence A100583: 8, 44, 124, 268, 492, 816, 1256, 1832, 2560, 3460, 4548, 5844, 7364, 9128, 11152, 13456, 16056, 18972, 22220, 25820, 29788, 34144, 38904, 44088, 49712, 55796, 62356, 69412, 76980, 85080, 93728, 102944, 112744, 123148, 134172, 145836.)