When both sides of the triangle are divided into an equal number of steps
(let's call this number -- n), the number of triangles is n^3 (n in the
third power). For the example you give in your page n=3 and the answer is
3^3 = 27.
When sides are subdivided into a different number of subdivisions, say, n
and m, the number of triangles is equal to
1
--- m * n (m + n)
2
which is integer for any integer m and n.
In J language (see http://www.jsoftware.com/ for description and download)
the first formula is coded and invoked as
nt =: ^&3
nt 3
27
The second formula is coded and invoked as
nt =: *-:@*+
3 nt 3
27
2 nt 5
35
The first variant of the program is three characters, the second is 6
characters.
It took me 15-20 minutes of drawing rectangles to derive the formula.
J is an array-oriented language, descendent of APL. Therefore, the above
programs (without change) can indeed be used to process millions of
rectangles very fast. In order to achieve this the arguments must be
arrays (of equal length in the second case). For example:
(3 2) nt (3 5)
27 35
How the formula was developed:
I've put (in the thread of livejournal I referenced,
http://www.livejournal.com/users/dr_klm/51584.html?thread=435072#t435072)
a scan of the page, where I drew triangles during those "15-20 minutes".
The direct link is here: http://galaxy.fzu.cz/~metlov/Triangles_Deriv.gif
I do not know it that will be enough to communicate the basic idea used
for deriving the formula. On the other hand I do not have time to explain
it to the arbitrary level of detalization.
The interesting part of the scan occupies the lower left quarter of the
page. Triangles are counted separately for two lower corners of the big
triangle (left and right) and then the result is multiplied by 2 (if n=m),
or added up with exchanging n<->m (if n!=m). To count triangles for one
corner I sum up the triangles, occupying all single sub-sectors, the
triangles, occupying all pairs of two consecutive sub-sectors, ... three
sub-sectors... etc... In this sum, the triangles, which include both left
and right corners of the big triangle are counted with weight 1/2 (to note
that they will be counted again, in the sum for the other corner).
I run this procedure for n=3, m=3 approximately in the middle of the
scanned page. Then, by induction, write a general formula with the sum.
The sum is nothing else but an arithmetic progression, which is
immediately summed up. Then, with very basic algebra the final formulas
are obtained.