Número de maneras de dividir un rectángulo en n sub-rectángulos

Question

¿De cuántas maneras se puede dividir un rectángulo mediante líneas verticales u horizontales en n ¿sub-rectángulos? Al principio pensé que sí:

      f(n) = 4f(n-1) - 2f(n-2)  
where f(0) = 1  
  and f(1) = 1 

pero la relación de recurrencia sólo cuenta los casos en los que al menos un lado (ya sea superior, inferior, izquierdo o derecho del rectángulo original) no está dividido en sub-rectángulos. Hay muchas otras particiones que no pertenecen a esos casos simples como

[EDITAR ImageShack ha eliminado la imagen. Uno de los casos es la sexta partición cuando n = 4 en la imagen en la respuesta aceptada a continuación].

Cualquier otra sugerencia de problemas relacionados es bienvenida. También es bueno saber cómo atravesar esta partición de manera eficiente.

Answer 1

Hice que mi estudiante, Tim Michaels, trabajara en esto. Llegamos a una complicada relación de recurrencia, indicada abajo. Las primeras respuestas son 1, 2, 6, 25, 128, 758, 5014, 36194, 280433, 2303918, 19885534, 179028087, 1671644720, 16114138846, 159761516110, 1623972412726, 16880442523007, 179026930243822, 1933537655138482, 21231023519199575, 236674460790503286, 2675162663681345170, 30625903703241927542, 354767977792683552908, 4154708768196322925749, 49152046198035152483150, 587011110939295781585102, 7072674305834582713614923. Obsérvese que estamos contando las rotaciones y las reflexiones como inclinaciones distintas. Un patrón interesante es que mod 2, hay una periodicidad de 8 veces que no entendemos y no podemos demostrar en general.

Aquí tienes una imagen de los casos n=1,2,3,4, con 1,2,6,25 tilings en cada caso.La forma de generarlos sistemáticamente es "meter" una línea vertical desde la derecha a todos los tilings construidos previamente de todas las formas posibles. Así se define la relación de recurrencia.

Bien, aquí está la recurrencia: Dejemos que $a_{\ell,j,m}$ sea el número de tilings distintos con $\ell$ azulejos, $j$ bordes que se encuentran con el lado derecho del cuadrado y $m$ Vértices de 4 valores. $$a_{\ell,j,m}=\sum_{p=1}^\ell(-1)^{p+1}\sum_{i=0}^m\sum_{n=1}^{\ell-1}\sum_{k=0}^{n-1}\alpha_{n,k,i,\ell,j,m,p} a_{n,k,i}$$ donde, dejando $t=m-i, s=\ell-n-p-t$ y $r=k+s+t+p-j$ , $$\alpha_{n,k,i,l,j,m,p}=\binom{r-1}{p-1}\binom{k-r+2}{p}\binom{s+r-1}{r-1}\binom{r-p}{t}.$$

Editar: He publicado un preprint que describe la relación de recurrencia aquí. Los comentarios son bienvenidos. ¿Sabe alguien que este tipo de cosas se pueden publicar en algún sitio?

Editar 2: Nathan Reading acaba de publicar un preimpresión. Encuentra una biyección entre los tilings genéricos (sin vértices de 4 valores) y un conjunto de permutaciones que evitan un determinado patrón.

Edita 3: El trabajo se ha publicado en el Anales de Combinatoria .

Answer 2

Este problema es tentador. Puede ser una versión "de juguete" de algunas investigaciones sustanciales en curso en topología, por lo que es valioso e interesante. Tiene análogos inmediatos en áreas de topología clásica, teoría de nudos, álgebra universal y teoría de campos topológicos. Por versión de juguete no quiero decir que sea necesariamente fácil de resolver, sino que puede utilizarse para presentar algunas ideas avanzadas de forma no técnica. Perdóname porque lo que sigue no es una respuesta a tu pregunta, sino una lista incoherente de problemas relacionados y posibles aplicaciones. Sólo espero que inspire a alguien de aquí a investigar las conexiones en topología algebraica. (Así, la comunidad wiki).

Estás pidiendo contar clases de equivalencia de encuadres de rectángulos parametrizados (donde un encuadre parametrizado es un encuadre con posiciones de línea precisas). En cierto sentido, este tipo de problema de enumeración surge a menudo en topología algebraica cuando se quiere entender una descomposición celular de un espacio complicado. Tomemos, por ejemplo, el espacio de n-planos en R^d. Estos espacios se llaman Grassmanianos y su topología se puede analizar descomponiéndolos en subconjuntos de varias dimensiones. Estos subconjuntos se llaman células de Schubert. Contar estas celdas de Schubert y entender cómo encajan fue un avance importante. Véanse las entradas de la wikipedia sobre Grassmannian y Geometría Enumerativa .

Tus espacios de encuadres rectangulares parametrizados (denotados quizás Fi^{n} donde i indexa las clases de equivalencia de los encuadres que tienen n sub-rectángulos) son análogos a las celdas del Grassmanniano, pero el espacio estratificado resultante es algún espacio universal de encuadres rectangulares parametrizados que incluye encuadres con un número arbitrariamente grande pero finito de sub-rectángulos. Es decir, cada uno de sus espacios de encuadres F (las clases de equivalencia que se quieren contar) representa una "celda" de alguna dimensión fija que degenera en encuadres de grado inferior en los límites. Estudiando cuidadosamente la forma simple de cada celda y cómo degeneran en otras celdas, podemos crear un espacio universal $F^{\infty}$ = $\bigcup$ $F^{n}_{i}$ ( modulo las relaciones de equivalencia del caso límite ).

A veces se puede abordar la topología de este espacio universal por otros medios, y ese conocimiento global puede utilizarse para contar el número de celdas necesarias en cada estrato. Por último, como señalas, los espacios tienen ciertas simetrías que pueden pasar al espacio completo de forma interesante.

Este truco de la estratificación aparece siempre Si quieres entender un espacio grande, encuentra una forma de dividirlo en estratos que encajen de forma analizable. O bien, encuentre un espacio relacionado que tenga una estratificación natural, analice este espacio estratificado y haga inferencias sobre el espacio original. Un gran uso, no trivial, de esto en los años 90 fue cuando Vassiliev se dio cuenta de que los nudos podían estudiarse analizando el espacio de los no nudos que admitía una estratificación muy clara (esencialmente estratificar los no nudos por el número de puntos en los que el mapa circular es no inyectivo) Vassiliev encontró una clara estructura topológica en este espacio y esto le permitió hacer afirmaciones sobre la estructura del conjunto de los nudos. Esto llevó a otros, como Kontsevich y Bar Natan, a proporcionar herramientas computacionales reales utilizando trucos para contar e integrar sobre las celdas. Por ejemplo, Mathworld tiene dos buenos artículos introductorios sobre Invariantes de Vassiliev y Integrales de Kontsevich .

En tercer lugar, su espacio de encuadre rectangular evoca la operada de los pequeños discos, que codifica una estructura algebraica. Véase la página de la wikipedia:
http://en.wikipedia.org/wiki/Operad_theory#.22Little_something.22_operads

Siempre que tengamos un conjunto de espacios topológicos tal que los elementos de los espacios puedan combinarse geométricamente para obtener espacios de mayor grado, esto indica que la geometría puede estudiarse utilizando técnicas del álgebra. Si te imaginas que pones variables en cada uno de los sub-rectángulos de tu marco, has descrito en cierto modo una operación algebraica. Imagina que cada uno de tus n-marcos parametrizados define un mapa de n entradas a 1 salida, una "operación n-aria". Supongamos además que la geometría impone alguna condición de consistencia que exige que cuando se coloca el resultado de una operación p-aria en uno de los sub-rectángulos de un marco q-ario, se obtiene justo lo que se obtendría de la correspondiente operación de marco (p+q-1)-ario. Esto significa que tu álgebra debe satisfacer ciertas relaciones estándar (quizás hasta la homotopía) y entonces estas operaciones pueden descender a operaciones en una teoría de cohomología adecuadamente definida. Es decir, la topología de tu espacio marco universal puede indexar varias operaciones que satisfacen exactamente ciertas relaciones. Véanse, por ejemplo, las entradas de ncatlab.org sobre operad , L-infinity-algebra y Álgebra A-infinita .

Answer 3

Todavía no tengo suficientes rep para comentar, así que haré este CW ya que no es una respuesta completa, sólo un comentario.

¿Superaría parte de la dificultad utilizando algún tipo de representación gráfica del rectángulo subdividido? Cada rectángulo es un vértice y una arista representa compartir un lado, es decir el primer rectángulo de arriba estaría representado por las aristas ${(1,2),(1,3),(2,4),(3,4)}$ y el segundo por ${(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)}$ numerando los rectángulos desde la parte superior izquierda a la inferior derecha. La parte complicada sería entonces implementar las operaciones de subdivisión por un segmento de línea vertical u horizontal. Empezar con líneas en lugar de segmentos podría ser prometedor.

Answer 4

He aquí una no-respuesta que puede resultar interesante y manejable.

Dada una configuración de rectángulos que embaldosan adecuadamente un rectángulo circundante, se puede representar el mosaico de varias maneras. Me vienen a la mente dos que llamaré C y LL. C representa cada rectángulo dando sus dimensiones (x-span y y-span) y las coordenadas para el centro del rectángulo, y LL hace lo mismo, excepto que especifica la coordenada para el vértice inferior izquierdo (en lugar del centro) de cada rectángulo.

Si hay muchos rectángulos en un mosaico, hay cierta redundancia en la forma LL de un mosaico. Por ejemplo, debería ser posible deducir las dimensiones del rectángulo de la esquina inferior izquierda del mosaico anotando las coordenadas almacenadas del rectángulo superior y del rectángulo a la derecha de este rectángulo de la esquina. No existen tales límites para el rectángulo superior derecho de un mosaico, pero quizá podría añadirse un "punto final" para indicar los valores máximos de x e y en el rectángulo en mosaico. Supongamos que añadimos dicho punto final, y dejemos que LL' sea una representación como LL que contenga las coordenadas inferiores izquierdas y el punto final, y NO contenga la información de la dimensión.

Afirmación 1: LL' es una representación equivalente a LL. Es decir, dada una representación en forma LL, se puede construir una representación en forma LL' y utilizarla para recrear el mosaico; a la inversa, se puede construir una forma LL a partir de una forma LL' para representar el mismo mosaico.

La afirmación 1 parece ser cierta; está claro cómo hacer una forma LL' a partir de una forma LL, mientras que para la inversa, debería ser posible comprobar todos los puntos inferiores de la izquierda para ver cuáles ayudarían a determinar las dimensiones para un rectángulo dado.

¿Es cierta la afirmación 1?

Ahora considere C y haga C' a partir de C olvidando de nuevo las dimensiones, excepto que puede proporcionar dos puntos finales que representen las esquinas superior derecha e inferior izquierda del rectángulo en mosaico.

Afirmación 2: C y C' son equivalentes en el sentido utilizado anteriormente para LL y LL' .

Está claro cómo obtener un formulario "C" a partir de un formulario "C". NO está claro que sea posible obtener un formulario C a partir de un formulario C' en el que no se tiene ninguna información de dimensión, excepto el rectángulo completo, tal y como lo implican los dos puntos finales.

¿Es cierta la afirmación 2?

Las afirmaciones 1 y 2 tienen relación con el problema anterior: puede ser posible enumerar mosaicos geométricamente no equivalentes con n rectángulos observando las formas normalizadas de C, C', LL o LL'. Además, puede ser ventajoso cambiar de forma de mosaico para determinar la equivalencia.

Hay variaciones interesantes que pueden ocurrir. Por ejemplo, C'' podría tener el centro del rectángulo alicatado en lugar de los dos puntos extremos, o incluso dar sólo las dimensiones de del rectángulo alicatado en lugar de las coordenadas de sus esquinas superior derecha e inferior izquierda. ¿Qué información se pierde con estas representaciones?

Meta-pregunta: ¿Hay alguna propiedad geométrica que explique por qué LL' utiliza menos información pero sigue siendo equivalente a C (suponiendo que la afirmación 1 es cierta), mientras que C' no lo es (suponiendo que la afirmación 2 es falsa)? ¿Se puede decir algo en general sobre qué propiedades de una forma de mosaico son necesarias para representar el mosaico de forma mínima y fiel?