Number of triangles in a square grid of unknown size

[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

 

[mmwave]

Hello Mator,

Thank you for sharing your problem with us. It seems like you have put a lot of thought into it and have made some good progress. I would approach this problem using mathematical principles and equations to help us find a solution.

First, let's define some variables:
- x and y: dimensions of the grid
- n: number of points in a group
- k: number of points in a line

To find the total number of groups of n points in a grid of size x by y, we can use the combination formula:

\binom{x\cdot y}{n} = \frac{(x\cdot y)!}{n!(x\cdot y-n)!}

This formula calculates the number of ways to choose n points from a grid of size x by y. However, this includes all possible combinations, including lines. To exclude lines, we can subtract the number of combinations of k points from the total.

So for your specific problem, we can modify the formula to be:

\binom{x\cdot y}{3} - \binom{x}{3}\cdot y - \binom{y}{3}\cdot x - \sum_{i=1}^{\infty} \binom{i}{3}\cdot 2

Where the summation represents the infinite series of diagonal lines with slope 1 or -1. We can also add summations for other diagonal lines with different slopes, as you have mentioned in your post.

I hope this helps and gives you some direction in finding a solution to your problem. Best of luck!