2
$\begingroup$

Per the title, I'm seeking the definition of a function $f(n, m)$ which evaluates to the number of lines made from exactly $n$ points which can be placed on a two-dimensional discrete, square grid of size $m \times m$.

My primary interest is the case where $n = 3$, as this is the answer I'm really after. I would've raised this question alone, however since I see that $n = 2$ has been answered already, I figured I might as well just generalize the question in hopes that there's some nice, elegant solution out there.

$\endgroup$
2

1 Answer 1

2
$\begingroup$

It seems that this has been answered here by S. Mustonen: PointsInGrid.pdf

There $f(n,m)$ is denoted by $L_n(m)$ and a formula would be $$L_n(m)=\frac{1}{2}[f(m,n+1)-2f(m,n)+f(m,n-1)]$$ for $$f(m,k)=\sum_{\substack{-m<kx<m\\-m<ky<m\\(x,y)=1}}(m-|kx|)(m-|ky|)$$

$\endgroup$
3
  • $\begingroup$ Apologies, but I haven't encountered that form of sigma expression. Can you please give a quick example as to how it should be expanded? $\endgroup$
    – Ben Burns
    May 31, 2016 at 9:39
  • $\begingroup$ I'm not quite sure what you mean: e.g. $L_2(2)=1/2(4-(2\cdot4)+(1+2+1+2+4+2+1+2+1))=6$ $\endgroup$ May 31, 2016 at 10:02
  • $\begingroup$ Thanks, that's perfect. I managed to work backward from your expansion to figure it out well enough to code it up in Python. I was a bit thrown by the bounds of the indexes being defined below the sigma rather than above it. $\endgroup$
    – Ben Burns
    May 31, 2016 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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