2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you mean by "unique" that intersection of the line with the grid contains exactly $n$ points? $\endgroup$ – მამუკა ჯიბლაძე May 31 '16 at 11:58
  • $\begingroup$ No. For example, for $f(3, 4)$, a line with zero slope which intersects $(0, 0)$ should count twice, as it would apply to the set $\{ (0, 0), (0, 1), (0, 2) \}$ as well as the set $\{ (0, 1), (0, 2), (0, 3) \}$ (assuming grid starts at $(0, 0)$ spanning into the positive quadrant, and each point is spaced 1 unit away from its neighbours). $\endgroup$ – Ben Burns May 31 '16 at 12:01
  • $\begingroup$ By "unique" I mean that ordering of the set doesn't matter. e.g. $\{ (0, 0), (0, 1) \}$ should be treated as equivalent to $\{ (0, 1), (0, 0) \}$ -- in retrospect, "distinct" would likely have been a better word choice. $\endgroup$ – Ben Burns May 31 '16 at 12:07
  • 1
    $\begingroup$ Shouldn't you have linked to your other, very similar question, mathoverflow.net/questions/240098/… ? $\endgroup$ – Gerry Myerson May 31 '16 at 12:56
  • 3
    $\begingroup$ Six edits in one hour. Hard to hit a moving target. $\endgroup$ – Gerry Myerson May 31 '16 at 12:58
3
$\begingroup$

Let $L_n(m)$ be defined as in this answer. 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}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.