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

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$ Dec 28 '11 at 14:30
  • $\begingroup$ @GerryMyerson yes I meant somthing different,seems u didnt open the image equilateral Triangle $\endgroup$ Dec 28 '11 at 14:38
  • $\begingroup$ 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. $\endgroup$ Dec 28 '11 at 14:41
  • $\begingroup$ @GerryMyerson I am sorry for that,I ll make changes now $\endgroup$ Dec 28 '11 at 14:43
  • $\begingroup$ 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. $\endgroup$ Dec 28 '11 at 14:44
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$ Jan 1 '12 at 8:01
  • $\begingroup$ $\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. $\endgroup$ Jan 1 '12 at 8:01
  • $\begingroup$ A194131 found it just now.One more thing where can we find general expression for a A194131 in OEIS? $\endgroup$ Jan 1 '12 at 8:46
  • $\begingroup$ @livinggourmand: A194131 has been updated with the formula. $\endgroup$ Jan 3 '12 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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