# There is a 5 by 5 matrix of points on a plane. How many triangles can be formed using points on this matrix?

There is a 5 by 5 matrix of points on a plane. How many triangles can be formed using points on this matrix?

-
Count the triples of points which do not give a triangle, and then subtract from the total. – Mariano Suárez-Alvarez Nov 1 '10 at 19:20

This is the obvious approach (to me, at least), and is mostly a matter of bookkeeping. To begin with, there are ${{5^2} \choose 3}$ sets of three points. However, some of these are colinear, which we don't want to count.

There are $2 \times 5 \times {5 \choose 3}$ horizontal or vertical sets of three colinear points. E.g.

 .xxx.   .....
.....   ...x.
.....   ...x.
.....   .....
.....   ...x.


There are $3+3+3+3$ sets of three colinear points with rise/run $\in {\pm 2, \pm 1/2}$.

 x....   ..x..
..x..   .....
....x   ...x.
.....   .....
.....   ....x

...x.   .....
.....   ....x
..x..   ..x..
.....   x....
.x...   .....


There are $2 \times {5 \choose 3}$ sets of three colinear points with rise/run $\in {\pm 1}$ along the main diagonal or main anti-diagonal.

 x....   .....
.x...   ...x.
..x..   ..x..
.....   .....
.....   x....


There are $4 \times {4 \choose 3}$ sets of three colinear points along the "shunted" main diagonal and main anti-diagonal (is there a better name for these diagonals?).

 .x...   ...x.   .....   .....
.....   ..x..   x....   .....
...x.   .....   .x...   ...x.
....x   x....   ..x..   ..x..
.....   .....   .....   .x...


Finally, there are these $4$ remaining:

 ..x..   ..x..   .....   .....
.x...   ...x.   .....   .....
x....   ....x   x....   ....x
.....   .....   .x...   ...x.
.....   .....   ..x..   ..x..


So there are ${{5^2} \choose 3}-2 \times 5 \times {5 \choose 3}-(3+3+3+3)-2{5 \choose 3}-4{4 \choose 3}-4=2148$ triangles that can be formed. I also checked this answer with some code in GAP.

[Here, I have assumed that you want to count congruent triangles separately.]

-
+1. I believe "antidiagonal" is already standard terminology, though I've seen the more elaborate "northeast-southwest diagonal" being used. – J. M. Nov 1 '10 at 23:53
Thanks for the answer. Beautifully explained.The question now indeed appears fairly simple but I am not a mathematician (or even a math student anymore) :) – Oposet Nov 2 '10 at 15:09