Número de ciclos en una rejilla de esa que cada ciclo de recorrer todas las líneas

Question

Definición: Un borde-es un componente de secuencia de algunos consecutivos colineal-segmentos.

Considere la posibilidad de una $n \times n$ la red, como la disposición de las $2n$ líneas. ¿Hay alguna idea sobre el número de ciclos simples con exactamente $2n$ edge-componentes tales que cada línea de la cuadrícula contiene exactamente un borde de un componente del ciclo? En otras palabras, los ciclos deben atravesar todas las líneas. Un ciclo simple es un ciclo que pasa a través de los nodos exactamente una vez.

En la imagen se puede ver un $7\times7$ la red, como el arreglo y la deseada 14 del ciclo.

Cualquier sugerencia u observación es útil.

Answer 1

¿Cuál es tu pregunta? Como hay líneas verticales de la $n$ y $n$ líneas horizontales, el circuito tendrá ciertamente al menos $2n$ segmentos. No es difícil probar que usted puede siempre hacerlo con $2n$ segmentos: imagine una escalera. ¿Buscas cómo muchos circuitos diferentes son posibles? ¿Son la rotación y la reflexión considerados?

Answer 2

Las estructuras que se desee contar son limitados auto-evitar la celosía de polígonos. Este documento describe algunos resuelto exactamente los modelos; es a partir de este libro, que es el estándar de referencia en estos tipos de problemas.

Normalmente celosía polígonos son basadas en su perímetro o área, pero su restricción naturalmente sugiere un recuento de estos $2n$-ágonos por el número de vértices o aristas como usted propone.

Si las visitas no tienen que ser de auto-evitar, entonces no se $\frac{n!(n-1)!}{2}$ de ellos; permutar las filas y columnas, y dividir por $2n$ debido a que ni el punto de partida ni la orientación es relevante.

Los seis primeros términos de ( $n=2\;\:..\: 7$ )$1, 4, 26, 240, 2918, 44424$. Aquí están las $26$ octágonos:

Esta secuencia es ahora A203935 en OEIS; el superseeker no pudo devolver cualquier información útil.