Math Forum / Mathematics / Undergraduate Math / June 2007

Brian

This was what was confusing about the OP's original post.  He did say "of these triangles" but his data implied that he was counting all triangles.  In his reply to my post he agreed with 22 so I think he wanted equilateral triangles of all sizes.  Either way I thought it was an interesting problem.

Chuck

On Fri, 22 Jun 2007 15:01:36 -0400, "Brian M. Scott"
<b.scott@csuohio.edu> wrote in
<news:3fr1yunu3uf0.3wuj604k5qdp.dlg@40tude.net> in
alt.math.undergrad:

Assume for convenience that the original triangle had sides
of length 1.  Let T(n) be the figure consisting of the
original triangle and the lines subdividing it into n^2
smaller triangles.  Let t(n, k) be the number of
downward-pointing triangles in T(n) whose sides have length
k/n (which I'll call k-triangles for short); as originally
worded, the problem asks for t(n, 1).  Finally, let t(n) be
the total number of downward-pointing triangles in T(n).

Either by my approach or by hagman's we have t(n, 1) =
C(n, 2), the binomial coefficient 'n choose 2'.  It's not
hard to see that t(n, 2) = C(n-2, 2): there are n-3
2-triangles with their bottom vertices on the base of T(n),
n-4 2-triangles with their bottom vertices on the next edge
up, and so on.  The same reasoning shows that t(n, 3) =
C(n-4, 2), t(n, 4) = C(n-6, 2), and so on.  Then

  t(n) = SUM[k > 0; t(n, k)]
       = SUM[k >= 0; C(n-2k, 2)]
       
The sums aren't really unbounded: C(j, k) = 0 if j < k, and
clearly t(n, k) = 0 if k > n, so after a certain point all
of the terms are 0, and we don't need to specify just when
that happens.  (In fact it's not hard to see that t(n, k) =
0 if k > n/2.)

The problem now is to reduce this sum of binomial
coefficients to a closed form.  A little thought shows that
the values of t(n) for even n are independent of those for
odd n.  For instance, t(6) = C(6, 2) + C(4, 2) + C(2, 2),
while t(7) = C(7, 2) + C(5, 2) + C(3, 2), with no terms in
common.  Thus, it's probably going to be easier to find
separate closed forms for t(2n) and t(2n+1).  There are
several straightforward ways to do this if one has the right
tools (e.g., finite differences); here's a longer but more
elementary approach.

Let's label each vertex of T(n) with the number of
downward-pointing triangles having that vertex as
bottom-most vertex.  For n = 6 and n = 7, for instance, we
get:

             0
           0   0
         0   1   0
       0   1   1   0
     0   1   2   1   0
   0   1   2   2   1   0
 0   1   2   3   2   1   0

           n = 6

               0
             0   0
           0   1   0
         0   1   1   0
       0   1   2   1   0
     0   1   2   2   1   0
   0   1   2   3   2   1   0
 0   1   2   3   3   2   1   0

             n = 7

It's not hard to see that increasing n by 1 always just adds
another row at the bottom of the previous triangle.  A
little more thought shows that these triangular arrays are
upper lefthand corners of an infinite rectangular array:

   0   1   2   3   4   5   6   7   8   9  10  11  12
 |--------------------------------------------------
0| 0   0   0   0   0   0   0   0   0   0   0   0   0
1| 0   1   1   1   1   1   1   1   1   1   1   1   1
2| 0   1   2   2   2   2   2   2   2   2   2   2   2
3| 0   1   2   3   3   3   3   3   3   3   3   3   3
4| 0   1   2   3   4   4   4   4   4   4   4   4   4
5| 0   1   2   3   4   5   5   5   5   5   5   5   5
6| 0   1   2   3   4   5   6   6   6   6   6   6   6
7| 0   1   2   3   4   5   6   7   7   7   7   7   7
8| 0   1   2   3   4   5   6   7   8   8   8   8   8
9| 0   1   2   3   4   5   6   7   8   9   9   9   9
10| 0   1   2   3   4   5   6   7   8   9  10  10  10
11| 0   1   2   3   4   5   6   7   8   9  10  11  11
12| 0   1   2   3   4   5   6   7   8   9  10  11  12

Let d(i, j) be the entry in row i, column j of this array.
(In fact d(i, j) = min{i, j}.)  Then

 t(n) = SUM[0 <= i,j & i+j <= n; d(i,j)]
      = SUM[i=0 to n; SUM[j=0 to n-i; d(i,j)]].

But it's more useful to notice that the individual terms in
this sum are the integers in the range from 0 through
floor(n/2) and to count how many times each appears:

 0 appears (n+1) + n = 2n + 1 times;
 1 appears (n-1) + (n-2) = 2n - 3 times;
 2 appears (n-3) + (n-4) = 2n - 7 times;
                   .
                   .
                   .
 k appears (n+1-2k) + (n-2k) = 2n - 4k + 1 times;
                   .
                   .
                   .
 m appears (n+1-2m) + (n-2m) = 2n - 4m + 1 times.
 
Thus,

 t(n) = SUM[k=1 to m; k(2n-4k+1)]
      = SUM[k=1 to m; k(2n+1)] - 4*SUM[k=1 to m; k^2]
      = m(m+1)(2n+1)/2 - 2m(m+1)(2m+1)/3
      = m(m+1)[(6n+3) - (8m+4)]/6
      = m(m+1)(6n-8m-1)/6.

If n = 2m, then t(n) = m(m+1)(2n-1)/6 = n(n+2)(2n-1)/24.  

If n = 2m+1, then t(n) = m(m+1)(2n+3)/6 =
(n-1)(n+1)(2n+3)/24.

Quick check: 6*8*11/24 = 22 = t(6), and 6*8*17/24 = 34 =
t(7), so the formulas yield the correct values for n = 6 and
n = 7, at least.  (In fact they agree with the expressions
that I got by other methods.)

A much easier problem, by the way, is to count the total
number of UPWARD-pointing triangles of all sizes; the answer
is surprisingly simple.

Brian

On Fri, 22 Jun 2007 14:11:08 EDT, John Mullins
<mjohn@yahoo.com> wrote in
<news:18438715.1182535898753.JavaMail.jakarta@nitrogen.mathforum.org>
in alt.math.undergrad:

[...]

[...]

Which can be simplified to n(n-1)/2.  Or you can get that
directly:

  SUM[i=1 to n; i - 1] = SUM[i=0 to n-1; i] =
  SUM[i=1 to n-1; i] = (n-1)n/2,
 
using at the last stage the familiar formula.

It's essentially equivalent.

Brian