How Many Triangles?

Date: 10/30/2001 at 21:04:04
From: ALiaa
Subject: Math algorithm using c++

If we join one point on each of the three sides of a triangle to 
make another triangle, there are three triangles with vertices 
pointing up. How many triangles will have vertices pointing up if 
there are n points? How can we find a mathematical relation between 
them? And how can we do this algorithm using c++ and graphing it 
using c++?

Thanks.

Date: 10/31/2001 at 00:56:30
From: Doctor Jeremiah
Subject: Re: Math algorithm using c++

Hi there!

It depends. Do you mean ALL the triangles that point up? Or do you 
mean all the small triangles that point up?

Considering n = 2, there are multiple ways to count triangles. If you 
count just the small ones that point up, then there are 6, but if you 
count ALL the triangles that point up, then there are 10 total.

If you want just the small triangles, you end up with this series:

 number of points     | 1 |  2 |  3 |  4 
 ---------------------|---|----|----|----
 number of triangles  | 3 |  6 | 10 | 15

Notice that 3 = 1+2, and 6 = 1+2+3, and 10 = 1+2+3+4, and so on.
Each number is the sum of all the numbers from 1 up to n+1.

Here is the formula for the generic sum of all the numbers up to a 
certain value j:

   j
 +---
  \
  /   i = j(j+1)/2
 +---
  i=1

And since j = n+1 for us then j(j+1)/2 = (n+1)(n+2)/2:

  n+1
 +---
  \
  /   i = (n+1)((n+1)+1)/2 = (n+1)(n+2)/2
 +---
  i=1

So (n+1)(n+2)/2 is the sum of all the numbers from 1 to n+1. The 
formula that creates the number of little triangles for any n is: 
(n+1)(n+2)/2

 n = 1     (n+1)(n+2)/2 = 3
 n = 2     (n+1)(n+2)/2 = 6
 n = 3     (n+1)(n+2)/2 = 10
 n = 4     (n+1)(n+2)/2 = 15

On the other hand, to figure out what the formula would be if you 
counted ALL the triangles, you first need to know how many triangles 
that means.

In this triangle (which has n = 3):

         +
        / \
       +---+
      / \ / \
     +---+---+
    / \ / \ / \
   +---+---+---+
  / \ / \ / \ / \
 +---+---+---+---+

There are the following triangles:

         +
        / \         there are 10 of this size triangle
       +---+

         +
        / \
       +---+        there are 6 of this size triangle
      / \ / \
     +---+---+

         +
        / \
       +---+
      / \ / \       there are 3 of this size triangle
     +---+---+
    / \ / \ / \
   +---+---+---+

         +
        / \
       +---+
      / \ / \
     +---+---+      there is 1 of this size triangle
    / \ / \ / \
   +---+---+---+
  / \ / \ / \ / \
 +---+---+---+---+

Do you see the pattern? Each triangle with n points has for the little 
triangles the sum of 1 to n+1, and it also has larger triangles that 
are also sums.

 number of points     |  0 |  1 |  2 |  3 |  4
 ---------------------|----|----|----|----|----
 number of triangles  |  1 |  4 | 10 | 20 | 35

So the TOTAL number of triangles for n = 3 is: 1+3+6+10 or the sum of 
the sums, which looks like:

   n                         k     j
 +---                      +---  +---
  \                         \     \
  /   (sum from 1 to j) =   /     /   i
 +---                      +---  +---
  j=1                       j=1   i=1

   k     j
 +---  +---
  \     \
  /     /   i
 +---  +---
  j=1   i=1

   k
 +---
  \
  /   j(j+1)/2
 +---
  j=1

   k
 +---
  \
  /   (j^2+j)/2
 +---
  j=1

       k                k
     +---             +---
      \                \
 1/2  /   j^2  +  1/2  /   j
     +---             +---
      j=1              j=1


 1/2  k(k+1)(2k+1)/6  +  1/2  k(k+1)/2

 k(k+1)(2k+1)/12  +  k(k+1)/4

 ( k(k+1)(2k+1) + 3k(k+1) )/12

 ( k(k+1)( (2k+1) + 3) )/12

 k(k+1)(2k+4)/12

 k(k+1)(k+2)/6

And since k = n+1 for us then k(k+1)(k+2)/6 = (n+1)(n+2)(n+3)/6. So 
(n+1)(n+2)(n+3)/6 is the sum of all the sums of the numbers from 1 to 
n+1. The formula that creates the number of ALL triangles for any n 
is: (n+1)(n+2)(n+3)/6

 n = 0     (n+1)(n+2)(n+3)/6 = 1
 n = 1     (n+1)(n+2)(n+3)/6 = 4
 n = 2     (n+1)(n+2)(n+3)/6 = 10
 n = 3     (n+1)(n+2)(n+3)/6 = 20
 n = 4     (n+1)(n+2)(n+3)/6 = 35
 n = 5     (n+1)(n+2)(n+3)/6 = 56

So in C it would be:

long triangle(long n)
{
    long i,sum=0;
    for(i=1;i<=n;i++)sum+=i;
    return sum;
}

long ALL_triangle(long n)
{
    long i,sum=0;
    for(i=1;i<=n;i++)sum+=triangle(i);
    return sum;
}

int main()
{
    long i;
    for(i=1;i<=5;i++)
        printf("n=%ld t=%ld all t=%ld\n",i,triangle(i+
1),ALL_triangle(i+1));
    return 0;
}

- Doctor Jeremiah, The Math Forum
  http://mathforum.org/dr.math/