# Thread: Number of possible triangle.

1. ## Number of possible triangle.

Q)triangle has n dots on each side. (as shown in fig) How many triangles can be formed (any size).
1st image (image002.jpg)

My incomplete solution

Ans)
If thr are n dots then total no of dots =n(n+1)/2
No of combination using 3 at a time = n(n+1)/2C3
but all set of 3 pts wont be ∆
some will be co linear points

image 2 (1111.jpg)

like x1,x2,x3 are coliner ON line AB , similarly on CD,EF n so on
n similarly on other side of ∆ BT, GH n so on & AT ,SJ n so on
combination of 3pts on AB = nC3
on CD = (n-1)C3
on EF = (n-2)C3
so total = nC3 +(n-1)C3+(n-2)C3………………………………….. 3C3
as there are 3 side therefor:
3x(nC3 +(n-1)C3+(n-2)C3………………………………….. 3C3)= 3(n∑ i=3 iC3) (the limits of summation didnt come properly)

so no . possible triange = n(n+1)/2C3 - 3(n∑ i=3 iC3)

but x1,x4,x6,x7 are also collinear...

dont know how to proceed
plz help!!!

2. ## Re: number of possible triangle .... plz give a look once

A recursive definition should solve the problem.

When n = 1, you have 0 triangles.
When n = 2, you have 1 triangle.

If n = k gives you x triangles, what does n = (k+1) give you?

If you can answer that, you can get the answer in general.

3. ## Re: number of possible triangle .... plz give a look once

Also...it matters if you only want equilateral triangles, I wasn't clear on that exactly. If you allow ANY triangle, then all you should have to do is calculate the number of points and eliminate cases where all three are colinear.

I'd build the cases up to maybe n = 3 or 4, then try to figure out the recursive portion which follows.

4. ## Re: number of possible triangle .... plz give a look once

Er, one more note. This is actually pretty tricky given the colinear issue...I see your problem now. This is significantly non-trivial, as you have to take all angles into account. It's possible, but it would be hard...you would have to get a formula to determine for a triangle of height h, how many angles produce 3 in a row, how many produce 4, 5, 6... I don't think this is straightforward at all. Can you post the verbatim question?

5. ## Re: number of possible triangle .... plz give a look once

1st of all .. i appreciate u gave time for this
when i read ur post i feel i m taken back in time where i thought of these things
spent 2 days now... :|

anyways this is my own question... not frm anywhere
and yes it can be any triangle.. not necessarily equilateral triangles

I did it till n =18 but still... many new colinear points were coming up..

but I do think there can be a general expression for this...
we are overlooking something ......

if u can show a direction.. i might do something on it
{i ll be sleeping now... its late .. might be a delay in my reply}

6. ## Re: number of possible triangle .... plz give a look once

Oh! That's a relief. If this is your own question then that explains a lot.

Congratulations are in order! You have discovered a well-established fact about math: there are many problems that are extremely easy to phrase, but difficult (and in some cases, though probably not this one, impossible) to solve.

Take a look at Fermat's Last Theorem sometime. Or for a bigger headache, the Collatz Conjecture (which may well be one of those impossible-to-solve problems for all we know). What you're asking for here is simple but realize that colinearity extends, as the triangle grows, toward an infinite number of angles. I don't know what the best method would be for attacking this problem, maybe geometry or even topology. I'm not about to try it, though.

7. ## Re: Number of possible triangle.

Originally Posted by livinggourmand
Q)triangle has n dots on each side. (as shown in fig) How many triangles can be formed (any size).
If $\displaystyle n\ge 3$ and $\displaystyle T(n)=\frac{n(n+1)}{2}$(i.e. the total number of point in the diagram) then the number of triangles is
$\displaystyle \binom{T(n)}{3}-\left[3 \cdot \sum\limits_{k = 3}^n \binom{k}{3} \right]$.

8. ## Re: Number of possible triangle.

Plato, how on Earth does that equation take the colinearity of arbitrary angles into account?

Example: if n = 5 or more, then colinear points appear at ~ 23.4 degrees (two levels, each level sqrt(3)/2, by four dots). The further you go, the more angles add colinearity. The poster is not asking for equilateral triangles or right triangles; they want all triangles, but no lines.

I can't believe that your recurrence is sufficient to handle that. For one thing, once you hit n = 8, you start generating 4 points colinear on each 23.4 degree angle, which is four triangles you have to eliminate from consideration for each line which contains 4 points... etc.

9. ## Re: Number of possible triangle.

Originally Posted by Annatala
Plato, how on Earth does that equation take the colinearity of arbitrary angles into account?
Example: if n = 5 or more, then colinear points appear at ~ 23.4 degrees (two levels, each level sqrt(3)/2, by four dots). The further you go, the more angles add colinearity. The poster is not asking for equilateral triangles or right triangles; they want all triangles, but no lines.
I admit that I am assuming that the larger triangle is equilateral where the points are equally spaced, given the posted diagram. Thus if $\displaystyle n=5$ then there are three sets of five colinear points, there are three sets of four colinear points, and there are three sets of three colinear points. So we remove any selection of three points that are colinear. So there are no angles to be considered.

Again the analysis is based on a grid of n points on each side of an equilateral triangle where the points are equally spaced.

There is a well-know problem in graph theory asking for the number of "triangles" is a graph. The quotes are for the fact that colinear is not an issue.

Now if we have n randomaly placed points on each side of the triangle, then of course there is no easy solution.

10. ## Re: Number of possible triangle.

You're ignoring some colinearities. Here, look:

Code:
    *
* *
@ * *
* * @ *
* * * * @
The larger the triangle becomes, the more of these there are at various angles. How are you accounting for them?

11. ## Re: Number of possible triangle.

@ Plato, this is an equilateral triangle with points equally spaced..
but still ...u r ignoring many co linear points...
if u see I gave an expression no . possible triange = n(n+1)/2C3 - 3(n∑ i=3 iC3)
which u also got...
if you proceed n=8,9,10 etc...
many other different cases of co linear points will appear...
u mentioned "There is a well-know problem in graph theory asking for the number of "triangles" is a graph"
will u please share a link of such problem... it might give me some idea...

@ Annatala
ur post "there are many problems that are extremely easy to phrase, but difficult (and in some cases, though probably not this one, impossible) to solve"
made me laugh ... all my frustration gone in sec
that may be the case......I think its difficult to solve this 1 but may b someone has a simple solution for this

I have many other questions like this for which I dont have answer... (all my own q )

12. ## Re: Number of possible triangle.

I'll take a look at it when I next have free time, which might be a week or two from now. I think there may be a reasonably simple formula for capturing what you want, but it will probably be a recursively dependent formula that takes a long while to calculate.

13. ## Re: Number of possible triangle.

Originally Posted by livinggourmand
@ Plato, this is an equilateral triangle with points equally spaced.. but still ...u r ignoring many co linear points...
if u see I gave an expression no . possible triange = n(n+1)/2C3 - 3(n∑ i=3 iC3)
which u also got...
if you proceed n=8,9,10 etc...
many other different cases of co linear points will appear...
u mentioned "There is a well-know problem in graph theory asking for the number of "triangles" is a graph"
will u please share a link of such problem... it might give me some idea...
Both of you are of course correct. I was clearly working with a model which was too small. However, I do think the key is to find out for each k from 3 to n how many "colinear sets" consist of exactly k points.

14. ## Re: Number of possible triangle.

If this were a square (or rhombus) instead of a triangle (half of a square, topologically speaking wrt the points lining up), it would be much easier to get the answer; as with the triangle, you can calculate the next point in a line from the previous, but there would also be an equal amount of room in all directions. If I solve this I'll probably start there.