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.

Improve this question
$\endgroup$
9
  • $\begingroup$ Do you mean by "unique" that intersection of the line with the grid contains exactly $n$ points? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented May 31, 2016 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
    Commented May 31, 2016 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
    Commented May 31, 2016 at 12:07
  • 1
    $\begingroup$ Shouldn't you have linked to your other, very similar question, mathoverflow.net/questions/240098/… ? $\endgroup$
    – Gerry Myerson
    Commented May 31, 2016 at 12:56
  • 3
    $\begingroup$ Six edits in one hour. Hard to hit a moving target. $\endgroup$
    – Gerry Myerson
    Commented May 31, 2016 at 12:58

1 Answer 1

Reset to default
2
$\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}.$$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .