I'm seeking the definition of some function $f(n,m)$ which evaluates to the number of distinct sets of $n$ collinear points which are selected from an evenly-spaced two-dimensional grid of $m \times m$ points?


Collinear in this case means that the points in the set fall exactly on some line with arbitrary slope, that is, it is not limited to horizontal, or vertical, or 45° diagonal lines.


It would also help to give some definition of an $f'(n,m)$ which only counted collinear sets which do not fall on a horizontal, vertical, or 45° line.




---


To make sure I'm asking the correct question, I'm attempting to code a solution to a variation of the n-queens problem which adds the constraint that no three queens may fall along the same line of arbitrary slope (inspired by the "no three in a line" problem). I'm attempting to encode the problem as constraints to a theorem prover. To check that I'm not creating redundant clauses, I'd like to calculate the expected number of clauses for this constraint. At present I believe I *should* be adding three clauses of the form $(a \land b) \implies \lnot c$ per triple of collinear spaces on the board.


I ask the question for the general case as I'm curious to quantify how many fewer clauses I'd need if the constraint were lessened to "no 4 in a line," or "no 5 in a line," and so on.



How many distinct sets of n collinear points are there in an evenly-spaced two-dimensional grid of m x m points?
Let $L\_n(m)$ be defined as in [this answer](https://mathoverflow.net/q/240105). Then the function $f(n,m)$ questioned here (aware that it is different from $f$ in the linked answer) can be computed as


$$f(n,m) = \sum\_{k=n}^{m} \binom{k}{n}\cdot L\_k(m).$$


This formula easily follows from the observation that from a line with (exactly) $k$ grid points, we can form $\binom{k}{n}$ different subsets of $n$ collinear points.


Now, let us compute $f'(n,m)$. The number of sets of $n$ collinear points on horizontal lines is $m\cdot \binom{m}{n}$, and so is the number of those on vertical lines. The number of sets of $n$ collinear points on 45° lines equals
$$\binom{m}{n} + 2\sum\_{k=n}^{m-1} \binom{k}{n} = \binom{m}{n} + 2\binom{m}{n+1}.$$
Hence,
$$f'(n,m) = f(n,m) - (2m+1)\cdot \binom{m}{n} - 2\binom{m}{n+1}.$$


