Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

An equilateral triangle has n equally spaced dots on each side. How many triangles can be formed (of any size)?

equilateral Triangle

Analysis
If there are n dots on each side then total no of dots =n(n+1)/2
Number of combination using 3 at a time =${n(n+1)/2 \choose 3}$
but all set of 3 pts wont be ∆ some will be co linear points
like x1,x2,x3 are coliner on line AB , similarly on CD,EF n so on2
n similarly on other side of ∆ BT, GH & so on
& AT ,SJ & so on
combination of 3 dots on AB = ${n \choose 3}$
on CD = ${n-1 \choose 3}$
on EF = ${n-2 \choose 3}$
so total = ${n \choose 3}+{n-1 \choose 3}+{n-2 \choose 3}....+{3 \choose 3}$
as there are 3 side
$\therefore \ $ total number of such combination
= $3\cdot\left[{n \choose 3}+{n-1 \choose 3}+{n-2 \choose 3}....+{3 \choose 3}\right]$
= $\left[3 \cdot \sum\limits_{k = 3}^n \binom{k}{3} \right]$
$\therefore \ $ total number of triangle
= ${n(n+1)/2 \choose 3}-\left[3 \cdot \sum\limits_{k = 3}^n \binom{k}{3} \right]$

But this is not the answer as x1,x4,x6,x7 are also collinear
also as the length of triangle increases ,we find more co-linearity at different

angles

share|improve this question
    
If there are $n$ dots on each side, then surely the total number of dots is $3n$, not $n(n+1)/2$. Or did you mean something else? –  Gerry Myerson Dec 28 '11 at 14:30
    
@GerryMyerson yes I meant somthing different,seems u didnt open the image equilateral Triangle –  livinggourmand Dec 28 '11 at 14:38
    
Maybe you should edit your question so that what it says is the same as what you mean for it to say. Or at least indicate that it is impossible to understand what you mean without opening that link. –  Gerry Myerson Dec 28 '11 at 14:41
    
@GerryMyerson I am sorry for that,I ll make changes now –  livinggourmand Dec 28 '11 at 14:43
    
Maybe you could calculate the answer for small values of $n$ and then look up the resulting sequence in the Online Encyclopedia of Integer Sequences. –  Gerry Myerson Dec 28 '11 at 14:44

1 Answer 1

up vote 4 down vote accepted

This question has previously been considered for triangles created by points in a square lattice; see here.

As with the square case, the challenge on the triangular lattice is determining the number of collinear triples. A000938 in OEIS gives the answer for the square lattice as

$$\left(2 \;\sum _{m=2}^n\; \sum _{k=2}^n (n-k+1) (n-m+1) \gcd (k-1,m-1)\right)-\frac{1}{6} n^2 (n^2-1).$$

This can be rearranged as

$$\left(2 \;\sum _{m=2}^n\; \sum _{k=2}^n (n-k+1) (n-m+1) (\gcd (k-1,m-1)-1)\right)+\frac{1}{3} n^2 (n-1)(n-2)$$

where each summand is the number of collinear triples with end-points offset by $(k-1,m-1)$, and the final term is the number of horizontal and vertical triples.

For the triangular lattice, a similar analysis gives the number of collinear triples as

$$ 3\; \sum _{k=2}^n \;\sum _{m=2}^k \frac{1}{2} (n-k+1) (n-k+2) (\gcd (k-1,m-1)-1). $$

After rearranging, we get the total number of triangles in the triangular lattice as

$$ \frac{1}{2} \left(n^2+n+2\right) \binom{n+2}{4} -\frac{3}{2}\; \sum _{k=2}^n\; \sum _{m=2}^k (n-k+1) (n-k+2) \gcd (k-1,m-1). $$

The first few values are $0, 1, 17, 105, 407, 1216, 3036, 6696, 13428, 25005, 43861, 73277$. As commented below, this is A194131 in OEIS.

share|improve this answer
    
Lets Take a case n=5 Triangle with n=5 Number of combination using 3 at a time =${5(5+1)/2 \choose 3}$ =${15 \choose 3}=455$. $\bullet$ On line AB, 5 points are colinear and same will be for other 2 sides. Total no. of set of 3 such points = $3*{5 \choose 3}=30$. $\bullet$ On line CD, 4 points are colinear and same will be for other 2 sides. Total no. of set of 3 such points = $3*{4 \choose 3}=12$. –  livinggourmand Jan 1 '12 at 8:01
    
$\bullet$ On line EF 3 points are colinear and same will be for other 2 sides. Total no. of set of 3 such points = $3*{3 \choose 3}=3$. $\bullet$ On line AF 3 points are colinear and same will be for other 2 sides. Total no. of set of 3 such points = $3*{3 \choose 3}=3$. Therefore total number of triangled $=455-(30+12+3+3)=407$. That is exactly what your generalized expression gives. Thanks a lot. –  livinggourmand Jan 1 '12 at 8:01
    
A194131 found it just now.One more thing where can we find general expression for a A194131 in OEIS? –  livinggourmand Jan 1 '12 at 8:46
    
@livinggourmand: A194131 has been updated with the formula. –  David Bevan Jan 3 '12 at 16:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.