# How many triangles can be created from a grid of certain dimensions?

How would you determine how many non-degenerate triangles can be drawn by connecting points in a $5 \times 5$ grid?

-
If you include "degenerate" triangles, in which the three vertices are on a straight line, then, since there are $25$ points in the grid, it would be just $\dbinom{25}{3}=2300$, the number of ways to choose three points out of $25$. So maybe the "hard" part of this problem is figuring out how many degenerate triangles must be subtracted from $2300$. – Michael Hardy Jan 10 '14 at 18:46
I should have been more specific. I want to know how to determine the number of non degenerate triangles that make up this grid. – user2081893 Jan 10 '14 at 18:47
Why not try a 2x2 grid, and then a 3x3, etc.? – Matthew Conroy Jan 10 '14 at 20:59
According to the answer given at the math completion I attended, the answer is 2148. So far no answer has given that number – user2081893 Jan 13 '14 at 1:10

Maybe the quickest way to do this is to take the number of triangles including degenerate ones and subtract the number of degenerate triangles.

The number of ways to choose three points out of 25 is $$\binom{25}{3} = 2300.$$

Now we consider how to count the number of degenerate triangles, i.e. those in which the three vertices are collinear. The possible slopes of the lines are $0,\infty,\pm1,\pm2,\pm\frac12$. The quickest way to see that is just staring at the grid. For example, with slope $1/3$, only two points on the grid can be found on the line.

With slope $0$, there are five possible lines and from one of those we must choose three points, so we get $$5\cdot\binom 5 3 = 50$$ degenerate triangles. And the same with slope $\infty$.

With slope $1$, we have two lines of length $1$, two of length $2$, two of length $3$, two of length $4$, and just one of length $5$. Hence the number of degenerate triangles is $$2\binom 1 3 + 2\binom 2 3 + 2\binom 3 3 + 2\binom 4 3 + 2\binom 5 3 = 30.$$ And the same with slope $-1$.

Now on to slope $1/2$. There are only three degenerate triangles with slope $1/2$. Call them $$\{(1,1),(3,2),(5,3)\} + (1,k) \text{ for }k=0,1,2.$$ Look at the grid any you'll see this. Similarly there are three with slope $-1/2$ and three with each of the slopes $\pm2$.

Now add them up: $$50+50+30+30+3+3+3+3 = 172.$$

Hence $$2300 - 172 = 2128.$$ non-degenerate triangles.

But you should check the details above closely since I haven't.

-
$2\binom 1 3 + 2\binom 2 3 + 2\binom 3 3 + 2\binom 4 3 + 2\binom 5 3 = 30$ not 58 – Nate Jan 10 '14 at 21:39
@Nate : Thank you. I've fixed that issue. Maybe there are others. – Michael Hardy Jan 10 '14 at 23:39
Comment left as answer: " Michael Hardy's answer has a small flaw. In his math, he is assuming that there is are 4 5-point diagonals (he adds 30 together) where it should be 30 + 10, as there are only 2 5-point diagonals in the problem. The answer is 2148." – user147263 Feb 12 '15 at 16:15
Norman is right. In the text, you say (correctly) "just one of length $5$", but in the corresponding equation you wrote a $2$ instead. The question has been asked in more general form in the meantime, leading to OEIS sequence A045996, which indeed gives $2148$ for $n=5$. – joriki Jul 27 '15 at 8:18

First choose 3 points arbitrarily this gives $\dbinom{25}{3}=2300$ possibly degenerate triangles.

Now we need to subtract off triples that all lie in a line:

There are 12 lines (5 vertical, 5 horizontal, and the main diagonals) containing 5 points these contribute $12\cdot\dbinom{5}{3}=120$ degenerate triangles.

There are 4 lines (off diagonals) containing 4 points. These contribute $4\cdot\dbinom{4}{3}=16$ degenerate triangles.

Finally, there are 12 lines with exactly 3 points (3 of each with slopes 2,-2, 1/2 , -1/2) which contribute 12 total degenerate triangles.

So 2300 total triangles minus 120+16+12 degenerate triangles gives 2152 nondegenerate triangles.

-
I think you missed some. – Michael Hardy Jan 10 '14 at 21:14
Ahh you are right, I missed the 4 lines of slope 1 or -1 with three points on them so it should be 2148 by my count now. – Nate Jan 10 '14 at 21:36
. . . and also those of slope $\pm1/2$ and $\pm2$. – Michael Hardy Jan 10 '14 at 23:40

It is as easy as it seems to be. This problem can be solved by combination and permutation techniques. What you need is that create as many as triangles as can be without creating a line (three collinear points will make a line out of a triangle). A triangle is formed with three noncollinear points. But there can be two collinear (here by collinear I mean being in the same row, column or diagonal) points. Just as combination you have 25 points (5x5 grid gives 25 slots) so 1st point could be from any of these i.e. 1st point can be placed in any of these 25 points. For the 2nd point there is no condition of any point being collinear or noncollinear (but let this pt be collinear with the 1st one although two pts are always collinear) so the second point has 24 points excluding the 1st one. So 2nd point can take any of these 24 points. For the third one, this point cannot be collinear to 1st and 2nd (if 1st and 2nd are collinear and if they are not then this can be collinear to either 1st or second and then consider this point to be the second one and the second point to be third point so that the three pts be non collinear) points both. So this must deduce some points from the remaining 23 slots. This deduce 3 points from the grid so the remaining slots are 20. This formula can be devised as for n*n grid Total no. of triangles are (n*n)*((n*n)-1)*(((n*n)-2)-(n-2)) = (n*n)*((n*n)-1)*((n*n)-n) . This formula can be used to calculate no. of triangles for n*n no. of grid.

So with the above formula and as said above the no. of triangles in a 5*5 grid becomes (5*5)*((5*5)-1)*((5*5)-5) = 25*24*20 just as the no. of slots I deduced above which comes out to be 12000 no. of triangles.

Also the number of triangles that comes out with this formula consists of too many repeated (by repeated I mean the triangles formed by the same points so the congruent triangles are excluded in this type) triangles. So how to remove these triangles which have repeated and also how many times have they be repeated. This is a simple trick which can be solved by factorialisation. We know that how many points a triangles consists of, obviously only 3 points (vertices). On a grid these three points will repeat themselves 3! (3 factorial) no. of times to form one triangle (6 triangles in all but all are same). So with this we can deduce that in every 6 triangles there are 5 fake ones and 1 real one. So the real : fake ratio becomes 1:5 . So the total no. of triangles omitting the fake ones becomes 1/6th the no. of triangles we got by above formula. So for a 5*5 grid total no. of triangles becomes 12000/6 = 2000. Yes 2000 different triangles but there can be and there are many congruent triangles.

This formula can be applied to other polygons to (with some modifications) and can be used. Also if someone fails to understand this answer I can post images here (although I don't know how as there is no image posting symbol like in SU).

-