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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/