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
$\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|)$$

| cite | improve this answer | |
$\endgroup$
  • $\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 '16 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 May 31 '16 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 '16 at 10:28

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.