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.

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
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|)$$

Improve this answer
$\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
    Commented 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$
    – Moritz Firsching
    Commented 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
    Commented May 31, 2016 at 10:28

You must log in to answer this question.

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