3
$\begingroup$

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

  • 0
    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?2011-12-28
  • 0
    @GerryMyerson yes I meant somthing different,seems u didnt open the image [equilateral Triangle](http://i.stack.imgur.com/B82Qh.jpg)2011-12-28
  • 0
    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.2011-12-28
  • 0
    @GerryMyerson I am sorry for that,I ll make changes now2011-12-28
  • 0
    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.2011-12-28
  • 0
    @Gerry that would be 3(n-1) I think? I think the question is not well expressed, but what I think it may mean is that there is a pyramid of dots in an array - a triangular grid pattern - making up an equilateral triangle with n dots per side. Then what seems to be wanted is the number of triangles (not necessarily equilateral) with vertices on the grid. The problem identified in the post seems to be that points in the grid can be collinear (no triangle) without the line joining them being parallel to one of the sides of the initial triangle.2011-12-28
  • 0
    @mark it ll be n(n+1)/2 for Ex n = 5 now base will have5 points above that 4 above that 3 .. 2 .. 1 so total no of points = 152011-12-28

1 Answers 1

4

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.

  • 0
    Lets Take a case **n=5** [Triangle with n=5](http://i.stack.imgur.com/6Ny1Z.jpg) 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$.2012-01-01
  • 0
    $\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.2012-01-01
  • 0
    [A194131](https://oeis.org/A194131) found it just now.One more thing where can we find general expression for a [A194131](https://oeis.org/A194131) in OEIS?2012-01-01
  • 0
    @livinggourmand: [A194131](https://oeis.org/A194131) has been updated with the formula.2012-01-03