¿Cómo podemos contar las líneas en un n-x n matriz rectangular?

Question

¿Hay una fórmula para el número de líneas que contienen exactamente dos puntos a través de una n x n matriz rectangular de puntos?

Answer 1

(Actualizado en respuesta a los comentarios de abajo:)

Me escribió un pequeño programa en Python para contar líneas en redes pequeñas, lo que me dio suficiente de datos para la búsqueda de OEIS y encontrar la respuesta en A018809.

Aquí está el código; el único verdadero truco es hacer todo en coordenadas proyectivas en lugar de estar en el mundo Cartesiano.

# Recuento de líneas a través de exactamente dos puntos en un n*n cuadrícula de puntos

# diccionario de asignación de líneas para el número de veces que se producen
líneas = {}

def cumplir((a,b,c),(d,e,f)):
 """De la línea a través de dos puntos o punto en dos líneas."""
 return ((b*f-c*e,c*d*f,a*e-b*d))

def mismo(l1,l2):
 """Hacer estas dos triples representan la misma recta?"""
 volver cumplir(l1,l2)==(0,0,0)

def sumar(l1):
 """Actualizar el número de veces que la línea l1 se ha generado."""
 si l1 == (0,0,0):
volver
 para la l2 en las líneas de:
 si mismo(l1,l2):
 líneas[l2] += 1
volver
 líneas[l1] = 1

for n in range(1,8):
 líneas = {}
 para un in range(n):
 para b in range(n):
 para c in range(n):
 para d in range(n):
agregar(cumplir((a,b,1),(c,d,1)))
 goodlines = 0
 para la línea,cuenta en las líneas.los elementos():
 si count == 2:
 goodlines += 1
 imprimir goodlines

Answer 2

Tal vez sería más fácil contar el número de líneas de nxn que pasan a través de más de dos puntos.

Lo que equivale a preguntar cómo muchos 2ix2j rectángulos hay en nxn, donde i y j son relativamente primos, excepto que sería sobre contar las líneas que pasan a través de 3 o más puntos.

Vamos a R_k = el número de ki x kj rectángulos en nxn, donde i y j son relativamente primos.

El número de líneas que circulan a través de al menos tres puntos en nxn es R_2 - R_3.

Answer 3

Para $n \geq 3$ el gradiente de estas líneas debe ser distinto de cero y finito. Así que debe ser posible dar una respuesta expresa como una suma sobre todos los gradientes que se reducen las fracciones a $q/p$ con $-n \leq q \leq n$, $\\,q \neq 0$ y $1 \leq p \leq n$.

Para un determinado gradiente $q/p$ usted puede contar el número de puntos de $(x,y) \in \{1,2,\ldots,n\}^2$ que cumplan:

• $1 \leq x+q \leq n$,
• $y+p \leq n$,
• $x-q \geq n+1$ o $x-q \leq 0$ o $y-q \leq 0$,
• $x+2q \geq n+1$ o $x+2q \leq 0$ o $y+2p \geq n+1$.

Los dos primeros puntos-puntos de asegurarse de que hay un segundo punto de $(x+q,y+p)$ sobre la línea. El segundo de dos punto-puntos de asegurarse de que no hay demasiados puntos en la línea, es decir, se garantiza $(x+2q,y+2p)$ $(x-q,y-p)$ son no tanto en $\{1,2,\ldots,n\}^2$.

Para darle una fórmula, el número de líneas que contienen exactamente dos puntos en $\{1,2,\ldots,n\}^2$ es \[\sum_ {n \leq q \leq n} \sum_{1 \leq p \leq n} \chi(q,p) |B_{q,p}|\] para $n \geq 3$ donde $\chi(q,p)=1$ si $\gcd(q,p)=1$, e $\chi(q,p)=0$ lo contrario, y $B_{q,p}$ es el subconjunto de a $\{1,2,\ldots,n\}^2$ para que los cuatro puntos-puntos están satisfechos.

Este debe tener $O(n^4)$ tiempo de complejidad (que no es gran cosa, pero es mejor que la mayoría de las fórmulas que suelen enfrentar).