# Number of triangles in a square grid of unknown size

1. Aug 13, 2013

### Mator

Hello.

I came up with this problem while I was waking up this morning, and some of the finer aspects have me pretty confused.

First off, I made the simplification of a square grid because I'm not yet ready to deal with non-square grids, but maybe we can get to that later. Here's where I got with the problem:

The number of groups of 3 points in a grid of unknown size is:

${x \cdot y \choose 3}$

Where $x$ and $y$ are the dimensions of the grid.

But we now need to subtract the number of 3 point groups that are lines and not triangles. We'll break these line groups into sections. The number of horizontal 3 point lines in a grid of unknown size (assuming x > 3) is:

${x \choose 3} \cdot y$

The number of vertical 3 point lines in a grid of unknown size (assuming y > 3) is:

${y \choose 3} \cdot x$

The number of diagonal lines increases following an infinite sum, as the number of types of such lines (each type corresponding to a certain slope) increases as the grid's size increases. Now I'm going to start going analytical because this is getting complicated. Below are grid sizes and the number of diagonal lines present in each grid.

Diagonal lines of slope 1 or -1:
3x3 grid: ${3 \choose 3} \cdot 2$
4x4 grid: ${3 \choose 3} \cdot 4 + {4 \choose 3} \cdot 2$
5x5 grid: ${3 \choose 3} \cdot 4 + {4 \choose 3} \cdot 4 + {5 \choose 3} \cdot 2$
6x6 grid: ${3 \choose 3} \cdot 4 + {4 \choose 3} \cdot 4 + {5 \choose 3} \cdot 4 + {6 \choose 3} \cdot 2$
7x7 grid: ${3 \choose 3} \cdot 4 + {4 \choose 3} \cdot 4 + {5 \choose 3} \cdot 4 + {6 \choose 3} \cdot 4 + {7 \choose 3} \cdot 2$
8x8 grid: ${3 \choose 3} \cdot 4 + {4 \choose 3} \cdot 4 + {5 \choose 3} \cdot 4 + {6 \choose 3} \cdot 4 + {7 \choose 3} \cdot 4 + {8 \choose 3} \cdot 2$

Diagonal lines of slope 2, -2, 1/2 or -1/2
5x5 grid: ${3 \choose 3} \cdot 4 \cdot 3$
6x6 grid: ${3 \choose 3} \cdot 4 \cdot 4 \cdot 2$
7x7 grid: ${3 \choose 3} \cdot 4 \cdot 2 + {3 \choose 3} \cdot 4 \cdot 5 + {4 \choose 3} \cdot 4 \cdot 4$
8x8 grid: ${3 \choose 3} \cdot 4 \cdot 2 \cdot 2 + {4 \choose 3} \cdot 4 \cdot 5 \cdot 2$

Diagonal lines of slope 3, -3, 1/3, or -1/3
7x7 grid: ${3 \choose 3} \cdot 4 \cdot 5$
8x8 grid: ${3 \choose 3} \cdot 4 \cdot 6 \cdot 2$

So these appear to be infinite series. I tried to write out the terms as logically as I could. And this as far as I've gotten... Anyone feel like helping out? :)

-Mator

Last edited: Aug 13, 2013