I have a task to formulate approach and calculate how many different lines are defined by points in 8x8 grid (so 2 or more points lies on the line). Points are evenly distributed ([0,0], [0,1], ..., [1,0], [1,1], ..., [7,7]).
I tried to partition into groups, use symmetry, think about it as sequences of numbers and then use combinatorics but it always explodes into a lot combinations and I get different results every time. Can someone point me how to approach this task?
On
Number the lattice points from $1$ to $N$. Count the number of lines that pass through lattice points $i$ and $j$ that do not pass through any lattice point $k$, $1 \le i \lt j \lt k \le N$.
That is obviously just restating the original requirement, and does not take advantage of the symmetries in the regular lattice, nor the combinatorial nature of the problem.
For a regular rectangular grid, I realized there is a much better approach, as I woke up this morning. (Your subconscious is your friend; let it do all the hard work! :)
Start with the simplest nondegenerate case, a 2×2 grid. This has six unique lines: two horizontal, two vertical, and two diagonal. (1×1 grid has no lines because there is not enough points, and single-row or single-column grids have exactly one line.)
Then, find out how many additional lines you get when you increase the width or height by one. Assume that you already know the number of lines in an $N \times K$ grid, and find out the number of unique lines added when $N$ is incremented by one. (Because of symmetries, this is the only case you need to find out.)
Let's say that you find that number in analytical form, say $\tau(N, K)$ when the grid size was $N \times K$ and $N$ is being incremented by one; and $N, K \ge 2$. The way/direction you grow the grid does not matter, and $\tau(N, K)$ is obviously symmetric with respect to $N$ and $K$. Thus, the total number of lines is $$\bbox{ T(N, K) = \begin{cases} 0, & N \le 1, K \le 1 \\ 1, & N = 1 \text{ and/or } K = 1 \\ 6, & N = 2, K = 2 \\ \displaystyle 6 + \sum_{n=2}^{N-1} \tau(n,2), & N \ge 3, K = 2 \\ \displaystyle 6 + \sum_{k=2}^{K-1} \tau(k,2), & N = 2, K \ge 3 \\ \displaystyle 6 + \sum_{n=2}^{N-1} \tau(n,2) + \sum_{k=2}^{K-1} \tau(k,N), & N \ge 3, K \ge 3 \\ \end{cases} }$$
That leaves the "hard" part, $\tau(N, K)$ (but we only need to consider it for $N \ge 2$, $K \ge 2$, as the grid size increases from $N \times K$ to $(N + 1) \times K$; for simplicity, let's assume it grows a new column, that $N$ is the number of columns in the old grid, and $K$ is the number of rows).
There is always at least one added line, the one along the new column of grid points. Every other new unique line $i$ has a slope $s_i \ne 0$. Because of symmetries, you'll find that for every positive $s_i$ there is a corresponding line with the same slope but negative, and vice versa. Therefore $\tau(N, K) = 1 + 2 p(N, K)$, and you only need to count new unique lines with positive slope, $p(N, K)$.
One way we can define $p(N, K)$ is just as a sum, where each summand indicates whether the line is new: $$\bbox{ p(N, K) = \sum_{n=1}^N \sum_{k=1}^{K} \sum_{i=1}^K U\bigr((n, k), (N + 1, i)\bigr) }$$ where $U\bigr((a, b), (c, d)\bigr)$ is 0 if the line between $(a,b)$ and $(c,d)$ passes through any lattice point $(i, j)$, and 1 if not (so such a line is new and unique).
To stop myself from finding the complete answer, I shall stop here. (More honestly, this is where I woke up, just as my subconscious was muttering something about $U$ and using greatest common denominators in finding whether there exists $j/i = h/w$, via $j = i h / w$ or something.)
EDIT: Found A018808 $0, 0, 6, 20, 62, 140, 306, 536, \color{green}{938}, 1492, 2306$
My counts were incorrect beyond 7x7.