counting triangles

[jay_shark]

Here is an original problem of my own that has to do with counting equilateral triangles .
Suppose you're given an equilateral triangle with side length n which is divided into sub-equilateral triangles in its usual manner .

A question of interest is to determine the total number of triangles facing upwards for any given nXn equilateral triangle .

[BruceZ]

[ QUOTE ]
Here is an original problem of my own that has to do with counting equilateral triangles .
Suppose you're given an equilateral triangle with side length n which is divided into sub-equilateral triangles in its usual manner .

[/ QUOTE ]

What does this mean? Are you referring to connecting the midpoints of each side to form 4 small triangles?


[ QUOTE ]
A question of interest is to determine the total number of triangles facing upwards for any given nXn equilateral triangle .

[/ QUOTE ]

What is an nXn equilateral triangle?

[jay_shark]

Yes bruce , so for a 2X2 triangle you connect the midpoints and there are 3 small triangles facing upwards of size 1X1 and one larger triangle facing upwards of size 2X2 .

Now the question is to find the number of triangles facing up for any nXn equilateral triangle where the triangles are divided in a similar fashion .

[Dromar]

nXn refers to the base X height of the triangles.

But this quesion seems difficult without more information. It seems like the answer is infinitely many, unless a limit is established as to how many times you can divide a given triangle into subtriangles.

If the given triangle is to be subdivided only once, then the answer depends on the orientation of the given triangle.
If the triangle is facing up, then the answer would be 4 (the original triangle, plus 3 of the 4 subtriangles).

Correct? Or am I misunderstanding the problem?

[Enrique]

I think the answer is (n+2) choose 3.

I did some cases and it looked like it was the sum of triangular numbers.
Here is why. The triangles of length 1 that are face upwards are: (1+2+3+...+n-1).
The triangles of length 2 are (1+2+3+...+(n-1)).
And you continue until you get 1 triangle of length n.
This sum comes out to (n)*(n+1)*(n+2) / 6.

[jay_shark]

Yes Enrique , it does work out to (n+2) choose 3 .

Here are two solutions . one is a straight forward approach while the other one is an elegant combinatorial proof .

solution 1) The number of triangles of
size 1 : 1+2+3 +...n = (n+1)c2
size 2 : 1+2+3+...n-1= nc2
size 3 : 1+2+3 +...n-2 = (n-1)c2
.
.
.
size n : 1 .

The total number of up triangles is 2c2 +3c2+4c2+...(N+1)c2 . Much to my surprise , this works out to (N+2)c3 using pascals identity . That is , Nck+ Nc(K+1)= (N+1)c(K+1)

using induction , assume it's true for K . Then show it's true for K+1 .

2c2+3c2+...Kc2 +(K+1)c2 = (K+1)C3 + (K+1)C2 .

rhs is (K+2)C3 and we're finished .

solution 2 ) Here is a very nice combinatorial solution.

Consider the numbers 1,2,3 ...,n,n+1 ,n+2

The number of ways of selecting subsets of size 3 is (n+2)c3 . Consider the first element in the subset of size 3 from left to right . This tells us the size of the triangle in question . The second element subtract the first element tells us which row the triangle of size k is in . Finally , the third element subtract the second element tells us where along the row that triangle is in .

For instance , if you select 2,5,9 then this tells you that the triangle is of size 2. 5-2=3 tells us that the triangle is in the third row . 9-5=4 tells us that the triangle is the fourth triangle from left to right along that row . Put it all together and we can give a representation to each up triangle using this combinatorial argument .

I'm very proud of that solution :P

[Enrique]

Yeah, your straightforward approach is like my proof.

The second solution was beautiful though. Thanks for sharing.

[thylacine]

Now do this one:

for integers k, n (k>0, n>=0) find the number of solutions to equation

a_1+a_2+...+a_k=n

where a_1,a_2,...,a_k are non-negative integers. (Similar idea to your solution 2, or look in a combinatorics book.)

[jay_shark]

Here is the answer thylacine .

_ _ _ | _ _ _ _ | _ _ = 9


This would be 3+ 4 +2 = 9 with n=9 and a1 , a2 , a3 for ai>0

The total number of ways of having 2 divisors for 3 unknowns is (9-1 )c (3-1) Notice there are n-1 spaces between adjacent points .

In general the total number of solutions is (n-1)C (r-1) .

Here is another follow up question :

Find the number of solutions to distinct non-negative integer valued vectors satisfying

a1 +a2 +...ar = n with ai>= 0

[thylacine]

Use generating functions.