Hispanopedia Wiki
Articulo de referencia

Poliomino

Los 18 pentominós de una sola cara , incluyendo 6 pares simétricos. Un poliomino es una figura geométrica plana y conexa , formada al unir un número finito de cuadrados unitario...

Hispanopedia WikiContenido en espanolLectura gratuita
Los 18 pentominós de una sola cara , incluyendo 6 pares simétricos.

Un poliomino es una figura geométrica plana y conexa , formada al unir un número finito de cuadrados unitarios borde con borde. Es una poliforma cuyas celdas son cuadrados . Puede considerarse un subconjunto finito y conexo del teselado cuadrado regular .

Los poliominós se han utilizado en rompecabezas populares desde al menos 1907, y la enumeración de pentominós se remonta a la antigüedad. [ 1 ] Muchos resultados con piezas formadas por 1 a 6 cuadrados se publicaron por primera vez en Fairy Chess Review entre los años 1937 y 1957, bajo el nombre de "problemas de disección". El nombre poliominó fue inventado por Solomon W. Golomb en 1953, [ 2 ] y fue popularizado por Martin Gardner en una columna de " Juegos Matemáticos " de noviembre de 1960 en Scientific American . [ 3 ]

Relacionados con los poliominós se encuentran los polidiamantes , formados por triángulos equiláteros ; los polihexágonos , formados por hexágonos regulares ; y otras poliformas planas . Los poliominós se han generalizado a dimensiones superiores mediante la unión de cubos para formar policubos , o hipercubos para formar polihipercubos.

En física estadística , el estudio de los poliominós y sus análogos de dimensiones superiores (a los que a menudo se hace referencia como animales reticulares en esta literatura) se aplica a problemas de física y química. Los poliominós se han utilizado como modelos de polímeros ramificados y de cúmulos de percolación . [ 4 ]

Los poliominós también aparecen en el álgebra conmutativa . En este contexto, un poliominó puede usarse para definir un ideal binomial generado por 2-menores internos en un anillo de polinomios cuyas variables corresponden a los vértices del poliominó, generalizando los ideales determinantes clásicos de matrices. [ 5 ] [ 6 ]

Como muchos rompecabezas de matemáticas recreativas , los poliominós plantean numerosos problemas combinatorios . El más básico consiste en enumerar poliominós de un tamaño determinado. No se ha encontrado ninguna fórmula, salvo para clases especiales de poliominós. Se conocen varias estimaciones y existen algoritmos para calcularlas.

Los poliominós con agujeros resultan inconvenientes para algunos propósitos, como los problemas de teselado. En ciertos contextos, se excluyen los poliominós con agujeros, permitiendo únicamente poliominós simplemente conexos . [ 7 ]

Enumeración de poliominós

Poliominós libres, unilaterales y fijos

Hay tres formas comunes de distinguir los poliominós para su enumeración: [ 8 ] [ 9 ]

  • Los poliominós libres se distinguen cuando ninguno es una transformación rígida ( traslación , rotación , reflexión o reflexión con deslizamiento ) de otro (piezas que se pueden levantar y voltear). Trasladar, rotar, reflejar o reflejar con deslizamiento un poliominó libre no altera su forma.
  • Los poliominós de una sola cara se distinguen cuando ninguno es una traslación o rotación de otro (piezas que no se pueden voltear). Trasladar o rotar un poliominó de una sola cara no altera su forma.
  • Los poliominós fijos se distinguen cuando ninguno es una traslación de otro (piezas que no se pueden voltear ni rotar). Trasladar un poliominó fijo no cambia su forma.

La siguiente tabla muestra la cantidad de poliominós de varios tipos con n celdas.

Los poliominós fijos fueron enumerados en 2004 hasta n = 56 por Iwan Jensen, [ 10 ] y en 2024 hasta n = 70 por Gill Barequet y Gil Ben-Shachar. [ 11 ]

Los poliominós libres fueron enumerados en 2007 hasta n = 28 por Tomás Oliveira e Silva, [ 12 ] en 2012 hasta n = 45 por Toshihiro Shirakawa, [ 13 ] en 2023 hasta n = 50 por John Mason, [ 14 ] y en 2025 hasta n = 59 por Toshihiro Shirakawa. [ 15 ]

Las secuencias OEIS anteriores, con la excepción de A001419, incluyen el conteo de 1 para el número de poliominós nulos; un poliominó nulo es aquel que está formado por cero cuadrados.

Simetrías de los poliominós

El grupo diedral D₄ es el grupo de simetrías de un cuadrado. Este grupo contiene cuatro rotaciones y cuatro reflexiones. Se genera alternando reflexiones sobre el eje x y sobre una diagonal. Un poliominó libre corresponde a un máximo de ocho poliominós fijos, que son sus imágenes bajo las simetrías de D₄ . Sin embargo, estas imágenes no son necesariamente distintas: cuanta más simetría tenga un poliominó libre, menos contrapartes fijas distintas tendrá. Por lo tanto, un poliominó libre que sea invariante bajo algunas o todas las simetrías no triviales de D₄ puede corresponder a solo cuatro, dos o un poliominó fijo. Matemáticamente, los poliominós libres son clases de equivalencia de poliominós fijos bajo el grupo D₄ .

Los poliominós tienen las siguientes simetrías posibles; [ 16 ] en cada caso se da el número mínimo de cuadrados necesarios en un poliominó con esa simetría:

  • 8 poliominós fijos por cada poliominó libre:
    • sin simetría (4)
  • 4 poliominós fijos por cada poliominó libre:
    • simetría especular con respecto a una de las direcciones de las líneas de la cuadrícula (4)
    • simetría especular con respecto a una línea diagonal (3)
    • Simetría rotacional doble: C 2 (4)
  • 2 poliominós fijos por cada poliominó libre:
    • simetría con respecto a ambas direcciones de las líneas de la cuadrícula y, por lo tanto, también simetría rotacional doble: D 2 (2) (también conocido como el grupo de Klein de cuatro dimensiones )
    • simetría con respecto a ambas direcciones diagonales y, por lo tanto, también simetría rotacional doble: D 2 (7)
    • Simetría rotacional cuádruple: C 4 (8)
  • 1 poliomino fijo por cada poliomino libre:
    • toda simetría del cuadrado: D 4 (1).

Del mismo modo, el número de poliominós unilaterales depende de la simetría del poliominó de la siguiente manera:

  • 2 poliominós de una sola cara por cada poliominó libre:
    • sin simetría
    • Simetría rotacional doble: C 2
    • Simetría rotacional cuádruple: C 4
  • 1 poliomino de una sola cara por cada poliomino libre:
    • toda simetría del cuadrado: D 4
    • simetría especular con respecto a una de las direcciones de las líneas de la cuadrícula
    • simetría especular con respecto a una línea diagonal
    • simetría con respecto a ambas direcciones de las líneas de la cuadrícula y, por lo tanto, también simetría rotacional doble: D 2
    • simetría con respecto a ambas direcciones diagonales y, por lo tanto, también simetría rotacional doble: D 2 .

La siguiente tabla muestra la cantidad de poliominós con n cuadrados, ordenados por grupos de simetría.

[ 17 ]

Algoritmos para la enumeración de poliominós fijos

algoritmos inductivos

Cada poliominó de tamaño n + 1 se puede obtener añadiendo un cuadrado a un poliominó de tamaño n . Esto da lugar a algoritmos para generar poliominós de forma inductiva.

En pocas palabras, dada una lista de poliominós de tamaño n , se pueden agregar cuadrados junto a cada poliominó en cada posición posible, y el poliominó resultante de tamaño n + 1 se agrega a la lista si no es un duplicado de uno ya encontrado; las mejoras en el orden de la enumeración y el marcado de los cuadrados adyacentes que no deben considerarse reducen la cantidad de casos que deben verificarse para detectar duplicados. [ 18 ] Este método puede utilizarse para enumerar poliominós libres o fijos.

Un método más sofisticado, descrito por Redelmeier, ha sido utilizado por muchos autores no solo para contar poliominós (sin necesidad de almacenar todos los poliominós de tamaño n para enumerar los de tamaño n +1), sino también para demostrar límites superiores en su número. La idea básica consiste en comenzar con un solo cuadrado y, a partir de ahí, añadir cuadrados de forma recursiva. Dependiendo de los detalles, puede contar cada n -ominó n veces, una vez desde cada uno de sus n cuadrados, o bien contarlo solo una vez.

La implementación más sencilla consiste en añadir un cuadrado a la vez. Comenzando con un cuadrado inicial, numera los cuadrados adyacentes, en el sentido de las agujas del reloj desde arriba, del 1 al 4. Ahora elige un número entre 1 y 4 y añade un cuadrado en esa posición. Numera los cuadrados adyacentes sin numerar, comenzando con el 5. Luego, elige un número mayor que el anterior y añade ese cuadrado. Continúa eligiendo un número mayor que el del cuadrado actual, añadiéndolo y numerando los nuevos cuadrados adyacentes. Cuando se hayan creado n cuadrados, se habrá creado un n -ominó.

Este método garantiza que cada poliominó fijo se cuente exactamente n veces, una vez por cada casilla inicial. Se puede optimizar para que cuente cada poliominó solo una vez, en lugar de n veces. Partiendo de la casilla inicial, declárela como la casilla inferior izquierda del poliominó. Simplemente no numere ninguna casilla que esté en una fila inferior o a la izquierda de la casilla en la misma fila. Esta es la versión descrita por Redelmeier.

Si se desea contar los poliominós libres, se pueden verificar las simetrías después de crear cada n- ominó. Sin embargo, es más rápido [ 19 ] generar poliominós simétricos por separado (mediante una variación de este método) [ 20 ] y así determinar el número de poliominós libres mediante el lema de Burnside .

Método de matriz de transferencia

Actualmente, los algoritmos más efectivos pertenecen al paradigma de la matriz de transferencia. Se les puede llamar algoritmos de matriz de transferencia (TMA, por sus siglas en inglés). Andrew Conway [ 21 ] implementó por primera vez un TMA en la década de 1990 y calculó 25 términos de la secuencia fija de poliominós ( A001419 en la OEIS). Iwan Jensen perfeccionó los métodos de Conway e implementó un TMA en paralelo por primera vez en un par de artículos a principios de la década de 2000. [ 22 ] [ 23 ] Calculó 56 términos. Debido a este trabajo, cualquier TMA a veces también se denomina algoritmo de Jensen. En 2024, Gill Barequet y su estudiante Gil Ben-Shachar hicieron otra mejora al ejecutar un TMA en una rotación de 45° de la cuadrícula cuadrada, que es un problema equivalente pero computacionalmente más fácil. [ 24 ] Este enfoque tiene el récord de conteo de poliominós, con 70 términos.

Por lo general, los TMA son mucho más rápidos que los métodos anteriores, pero su tiempo de ejecución sigue siendo exponencial en n . En términos generales, esto se logra fijando un ancho (en el caso de la diagonal, un ancho diagonal) y contando los poliominós que caben en rectángulos de ese ancho. Si se hace esto, solo es necesario llevar un registro del contorno de un poliominó, y dado que varios poliominós pueden corresponder a un solo contorno, este enfoque es más rápido que uno que genere todos los poliominós. Repitiendo esto para cada ancho se obtienen todos los poliominós.

Si bien tiene un excelente tiempo de ejecución, la desventaja es que este algoritmo utiliza cantidades exponenciales de memoria (se necesitan muchos gigabytes de memoria para n superior a 50), es mucho más difícil de programar que los otros métodos y actualmente no se puede utilizar para contar poliominós libres.

Crecimiento asintótico del número de poliominós

poliominós fijos

Los argumentos teóricos y los cálculos numéricos respaldan la estimación del número de poliominós fijos de tamaño n.

Anorte∼doλnortenorte{\displaystyle A_{n}\sim {\frac {c\lambda ^{n}}{n}}}

donde λ = 4,0626 y c = 0,3169. [ 25 ] Sin embargo, este resultado no está probado y los valores de λ y c son solo estimaciones.

Los resultados teóricos conocidos no son tan específicos como esta estimación. Se ha demostrado que

límitenorte→∞(Anorte)1norte=λ{\displaystyle \lim _{n\rightarrow \infty }(A_{n})^{\frac {1}{n}}=\lambda }

Existe. En otras palabras, A n crece exponencialmente . El mejor límite inferior conocido para λ , hallado en 2016, es 4,00253. [ 26 ] El mejor límite superior conocido es λ < 4,5252 . [ 27 ]

Para establecer una cota inferior, un método sencillo pero muy eficaz es la concatenación de poliominós. Definimos el cuadrado superior derecho como el cuadrado más a la derecha de la fila superior del poliominó. Definimos el cuadrado inferior izquierdo de forma similar. Entonces, el cuadrado superior derecho de cualquier poliominó de tamaño n se puede unir al cuadrado inferior izquierdo de cualquier poliominó de tamaño m para producir un ( n + m )-ominó único. Esto prueba que A n ·A m ≤ A n + m . Usando esta desigualdad, se puede demostrar que λ ≥ ( A n ) 1/ n para todo n . Los refinamientos de este procedimiento combinados con datos para A n producen la cota inferior dada anteriormente.

El límite superior se alcanza generalizando el método inductivo de enumeración de poliominós. En lugar de añadir un cuadrado a la vez, se añade un grupo de cuadrados a la vez. Esto se suele describir como añadir ramitas . Al demostrar que cada n -ominó es una secuencia de ramitas, y al demostrar los límites de las combinaciones de ramitas posibles, se obtiene un límite superior para el número de n -ominós. Por ejemplo, en el algoritmo descrito anteriormente, en cada paso debemos elegir un número mayor, y se añaden como máximo tres números nuevos (ya que como máximo tres cuadrados sin numerar son adyacentes a cualquier cuadrado numerado). Esto se puede utilizar para obtener un límite superior de 6,75. Utilizando 2,8 millones de ramitas, Klarner y Rivest obtuvieron un límite superior de 4,65, [ 28 ] que posteriormente fue mejorado por Barequet y Shalah a 4,5252. [ 27 ]

Poliominós libres

Las aproximaciones para el número de poliominós fijos y libres están relacionadas de forma sencilla. Un poliominó libre sin simetrías (rotación o reflexión) corresponde a 8 poliominós fijos distintos, y para valores grandes de n , la mayoría de los n -ominós no presentan simetrías. Por lo tanto, el número de n -ominós fijos es aproximadamente 8 veces mayor que el número de n -ominós libres. Además, esta aproximación es exponencialmente más precisa a medida que n aumenta. [ 16 ]

Clases especiales de poliominós

Se conocen fórmulas exactas para enumerar poliominós de clases especiales, como la clase de poliominós convexos y la clase de poliominós dirigidos .

La definición de un poliomino convexo difiere de la definición habitual de convexidad , pero es similar a la definición utilizada para la envoltura convexa ortogonal . Se dice que un poliomino es verticalmente o columnarmente convexo si su intersección con cualquier línea vertical es convexa (es decir, cada columna no tiene agujeros). De manera similar, se dice que un poliomino es horizontalmente o filarmente convexo si su intersección con cualquier línea horizontal es convexa. Se dice que un poliomino es convexo si es filarmente y columnarmente convexo. [ 29 ]

Se dice que un poliomino es dirigido si contiene un cuadrado, conocido como raíz , de tal manera que se puede llegar a cualquier otro cuadrado mediante movimientos de un cuadrado hacia arriba o hacia la derecha, sin salir del poliomino.

Los poliominós dirigidos, [ 30 ] los poliominós convexos de columna (o fila), [ 31 ] y los poliominós convexos [ 32 ] se han enumerado eficazmente por área n , así como por otros parámetros como el perímetro, utilizando funciones generadoras .

Un poliominó es igual si su área es igual a su perímetro. Un poliominó igual debe estar formado por un número par de cuadrados; cualquier número par mayor que 15 es posible. Por ejemplo, el poliominó de 16 cuadrados (4  ×  4) y el de 18 cuadrados (3  ×  6) son ambos iguales. Para los poliominós con 15 cuadrados o menos, el perímetro siempre supera el área. [ 33 ]

Teselado con poliominós

En matemáticas recreativas , a menudo se plantean desafíos para teselar una región prescrita, o todo el plano, con poliominós, [ 34 ] y se investigan problemas relacionados en matemáticas y ciencias de la computación .

Recubrimiento de regiones con conjuntos de poliominós

Los rompecabezas suelen pedir que se recubra una región determinada con un conjunto dado de poliominós, como los 12 pentominós. Los libros de Golomb y Gardner contienen muchos ejemplos. Un rompecabezas típico consiste en recubrir un rectángulo de 6×10 con los doce pentominós; en 1960 se encontraron 2339 soluciones para este problema. [ 35 ] Cuando se permiten múltiples copias de los poliominós del conjunto, Golomb define una jerarquía de diferentes regiones que un conjunto puede recubrir, como rectángulos, franjas y todo el plano, y demuestra que la posibilidad de que los poliominós de un conjunto dado recubrir el plano es indecidible , mediante la correspondencia entre conjuntos de teselas de Wang y conjuntos de poliominós. [ 36 ]

Debido a que el problema general de teselar regiones del plano con conjuntos de poliominós es NP-completo , [ 37 ] teselar con más de unas pocas piezas se vuelve rápidamente intratable y, por lo tanto, se requiere la ayuda de una computadora. El enfoque tradicional para teselar regiones finitas del plano utiliza una técnica en ciencias de la computación llamada retroceso . [ 38 ]

En los Sudokus Jigsaw, una cuadrícula cuadrada se cubre con regiones en forma de poliominó (secuencia A172477 en el OEIS ) .

Recubrimiento de regiones con copias de un único poliomino

Otro tipo de problemas pregunta si las copias de un poliominó dado pueden recubrir un rectángulo y, de ser así, qué rectángulos pueden recubrir. [ 39 ] Estos problemas se han estudiado extensamente para poliominós particulares, [ 40 ] y se dispone de tablas de resultados para poliominós individuales. [ 41 ] Klarner y Göbel demostraron que para cualquier poliominó existe un conjunto finito de rectángulos primos que recubre, de modo que todos los demás rectángulos que recubre pueden ser recubiertos por esos rectángulos primos. [ 42 ] [ 43 ] Kamenetsky y Cooke demostraron cómo varios poliominós disjuntos (llamados "agujeros") pueden recubrir rectángulos. [ 44 ]

Más allá de los rectángulos, Golomb estableció su jerarquía para los poliominós individuales: un poliominó puede cubrir un rectángulo, media tira, una tira doblada, una copia ampliada de sí mismo, un cuadrante, una tira, un semiplano , el plano completo, ciertas combinaciones o ninguna de estas opciones. Existen ciertas implicaciones entre estas opciones, tanto obvias (por ejemplo, si un poliominó cubre el semiplano, también cubre el plano completo) como menos evidentes (por ejemplo, si un poliominó cubre una copia ampliada de sí mismo, también cubre el cuadrante). Los poliominós de tamaño hasta 6 se caracterizan en esta jerarquía (con el estatus de un hexominó, que posteriormente se descubrió que también cubría un rectángulo, aún sin resolver en ese momento). [ 45 ]

En 2001, Cristopher Moore y John Michael Robson demostraron que el problema de cubrir un poliomino con copias de otro es NP-completo . [ 46 ] [ 47 ]

Recubrir el plano con copias de un solo poliomino

Los dos nonominós de teselado no cumplen el criterio de Conway.

También se ha discutido mucho sobre el recubrimiento del plano con copias de un solo poliominó. En 1965 se observó que todos los poliominós hasta los hexominós [ 48 ] y todos menos cuatro heptominós recubren el plano. [ 49 ] Posteriormente, David Bird estableció que todos menos 26 octominós recubren el plano. [ 50 ] Rawsthorne descubrió que todos menos 235 poliominós de tamaño 9 recubren el plano, [ 51 ] y estos resultados han sido extendidos a áreas mayores por Rhoads (hasta el tamaño 14) [ 52 ] y otros. Los poliominós que recubren el plano se han clasificado según las simetrías de sus recubrimientos y por el número de aspectos (orientaciones) en los que aparecen las piezas en ellos. [ 53 ] [ 54 ]

El estudio de qué poliominós pueden teselar el plano se ha facilitado utilizando el criterio de Conway : excepto dos no-ominós, todos los poliominós teseladores de hasta tamaño 9 forman un parche de al menos una pieza que lo satisface, siendo más frecuentes las excepciones de mayor tamaño. [ 55 ]

Varios poliominós pueden recubrir copias más grandes de sí mismos, y al repetir este proceso recursivamente se obtiene un recubrimiento del plano mediante reptiles. Por ejemplo, para cada entero positivo n , es posible combinar n² copias del L-trominó, L-tetrominó o P-pentominó en una única figura más grande similar al poliominó más pequeño del que se formó. [ 56 ]

Revestimiento de una figura común con varios poliominós

Una cifra de compatibilidad mínima para los pentominós T y W.

El problema de compatibilidad consiste en tomar dos o más poliominós y encontrar una figura que pueda ser recubierta con cada uno. La compatibilidad de poliominós se ha estudiado ampliamente desde la década de 1990. Jorge Luis Mireles y Giovanni Resta han publicado sitios web con resultados sistemáticos, [ 57 ] [ 58 ] y Livio Zucca muestra resultados para algunos casos complicados como tres pentominós diferentes. [ 59 ] El problema general puede ser difícil. La primera figura de compatibilidad para los pentominós L y X se publicó en 2005 y tenía 80 fichas de cada tipo. [ 60 ] Se ha demostrado que muchos pares de poliominós son incompatibles mediante agotamiento sistemático. No se conoce ningún algoritmo para decidir si dos poliominós arbitrarios son compatibles.

Poliominós en rompecabezas y juegos

Además de los problemas de teselado descritos anteriormente, existen rompecabezas matemáticos recreativos que requieren doblar un poliominó para crear otras formas. [ 61 ] [ 62 ] Gardner propuso varios juegos sencillos con un conjunto de pentominós libres y un tablero de ajedrez . [ 3 ] Algunas variantes del rompecabezas Sudoku utilizan regiones con forma que no son de poliominó en la cuadrícula. El videojuego Tetris se basa en los siete tetrominós de una sola cara (escritos como "Tetriminos" en el juego), y el juego de mesa Blokus utiliza todos los poliominós libres hasta los pentominós.

Etimología

La palabra poliominó y los nombres de los distintos tamaños de poliominó son todos derivaciones regresivas de la palabra dominó , una pieza de juego común que consta de dos cuadrados. Se cree que el nombre dominó para la pieza de juego proviene de la prenda de mascarada con lunares dominó , del latín dominus . [ 63 ] A pesar de este origen de la palabra, al nombrar los poliominós, la primera letra d- de dominó se interpreta de forma fantasiosa como una versión del prefijo di- que significa "dos", y se reemplaza por otros prefijos numéricos .

Véase también

  • La teoría de la percolación es el estudio matemático de subconjuntos aleatorios de cuadrículas de números enteros. Los componentes conexos finitos de estos subconjuntos forman poliominós.
  • Diagrama de Young , un tipo especial de poliomino utilizado en teoría de números para describir particiones enteras y en teoría de grupos y aplicaciones en física matemática para describir representaciones del grupo simétrico.
  • Blokus , un juego de mesa que utiliza poliominós.
  • Squaregraph es un tipo de grafo no dirigido que incluye como caso especial los grafos de vértices y aristas de poliominós.
  • Polycube , su análogo en tres dimensiones.

Notas

  1. ↑ Golomb ( Poliominós , Prefacio a la primera edición) escribe: "La observación de que hay doce patrones distintos (los pentominós) que se pueden formar con cinco piedras conectadas en un tablero de Go ... se atribuye a un antiguo maestro de ese juego".
  2. ↑ Golomb, Solomon W. (1994). Poliominós (2.ª  ed.). Princeton, Nueva Jersey: Princeton University Press. ISBN 978-0-691-02444-8.
  3. 1 2 Gardner, M. (noviembre de 1960). "Más sobre las formas que se pueden crear con dominós complejos (juegos matemáticos)". Scientific American . 203 (5): 186– 201. doi : 10.1038/scientificamerican1160-186 . JSTOR 24940703 . 
  4. ↑ Whittington, SG; Soteros, CE (1990). "Animales reticulares: resultados rigurosos y conjeturas descabelladas". En Grimmett, G.; Welsh, D. (eds.). Desorden en los sistemas físicos . Oxford University Press.
  5. ↑ J. Herzog, T. Hibi, H. Ohsugi, Binomial Ideals , Graduate Texts in Mathematics 279, Springer, 2018, Capítulo 8.
  6. ↑ AA Qureshi, “Ideales generados por 2-menores, colecciones de celdas y poliominós apilados”, Journal of Algebra 357 (2012), 279–303.
  7. ↑ Grünbaum, Branko ; Shephard, GC (1987). Tilings and Patterns . Nueva York: WH Freeman and Company. ISBN 978-0-7167-1193-3.
  8. ↑ Redelmeier, D. Hugh (1981). "Contando poliominós: otro ataque más" . Matemáticas Discretas . 36 (2): 191– 203. doi : 10.1016/0012-365X(81)90237-5 .
  9. ↑ Golomb, capítulo 6
  10. ↑ Iwan Jensen. "Series para animales reticulares o poliominós" . Archivado del original el 12 de junio de 2007. Consultado el 6 de mayo de 2007 .
  11. ↑ Barequet, Gill; Ben-Shachar, Gil (enero de 2024). «Conteo de poliominós, una revisión» . Actas del Simposio sobre Ingeniería y Experimentos de Algoritmos (ALENEX) de 2024: Conteo de poliominós, una revisión . Sociedad de Matemáticas Industriales y Aplicadas. págs. 133–143 . doi : 10.1137/1.9781611977929.10 . ISBN  978-1-61197-792-9.
  12. ↑ Tomás Oliveira e Silva. "Enumeraciones de animales en el teselado euclidiano {4,4}" . Archivado del original el 23 de abril de 2007. Recuperado el 6 de mayo de 2007 .
  13. ↑ "Cuadrado mágico armónico, enumeración de poliominós considerando la simetría" (PDF) .
  14. ↑ "Conteo de poliominós de tamaño 50" (PDF) .
  15. ↑ Shirakawa, Toshihiro (2025). "Enumeración de poliominós hasta tamaño N=59". arXiv : 2510.22446 [ math.CO ].
  16. 1 2 Redelmeier, sección 3
  17. ↑ Redelmeier, D. Hugh (1981). "Contando poliominós: Otro ataque más" . Matemáticas Discretas . 36 (2): 191– 203. doi : 10.1016/0012-365X(81)90237-5 .
  18. ↑ Golomb, págs. 73–79
  19. ↑ Redelmeier, sección 4
  20. ↑ Redelmeier, sección 6
  21. ↑ Conway, Andrew (1995). "Enumeración de series de percolación 2D mediante el método de red finita: teoría". Journal of Physics A: Mathematical and General . 28 (2): 335– 349. Bibcode : 1995JPhA...28..335C . doi : 10.1088/0305-4470/28/2/011 . Zbl 0849.05003 . 
  22. ↑ Jensen, Iwan (2001). "Enumeraciones de animales y árboles reticulares". Journal of Statistical Physics . 102 (1): 865– 881. arXiv : cond-mat/0007239 . Bibcode : 2001JSP...102..865J . doi : 10.1023/A:1004855020556 .
  23. ↑ Jensen, Iwan (2003). Counting Polyominoes: A Parallel Implementation for Cluster Computing . International Conference on Computer Science (ICCS). pp. 203– 212. doi : 10.1007/3-540-44863-2_21 . 
  24. ↑ Barequet, Gill; Ben-Shachar, Gil (2003). Counting Polyominoes, Revisited . Symposium on Algorithm Engineering and Experiments (SIAM). pp. 133– 143. arXiv : 2310.20632 . doi : 10.1137/1.9781611977929.1 . 
  25. ↑ Jensen, Iwan; Guttmann, Anthony J. (2000). "Estadística de animales reticulares (poliominós) y polígonos". Journal of Physics A: Mathematical and General . 33 (29): L257– L263. arXiv : cond-mat/0007238v1 . Bibcode : 2000JPhA...33L.257J . doi : 10.1088/0305-4470/33/29/102 . S2CID 6461687 . 
  26. ↑ Barequet, Gill; Rote, Gunter; Shalah, Mira. "λ > 4: Un límite inferior mejorado para la constante de crecimiento de los poliominós". Communications of the ACM . 59 (7): 88– 95. doi : 10.1145/2851485 .
  27. 1 2 Barequet, Gill; Shalah, Mira (2022). "Límites superiores mejorados en las constantes de crecimiento de poliominós y policubos" . Algorithmica . 84 (12): 3559– 3586. arXiv : 1906.11447 . doi : 10.1007/s00453-022-00948-6 .
  28. ↑ Klarner, DA; Rivest, RL (1973). "Un procedimiento para mejorar la cota superior del número de n -ominós" (PDF) . Revista Canadiense de Matemáticas . 25 (3): 585– 602. CiteSeerX 10.1.1.309.9151 . doi : 10.4153/CJM-1973-060-4 . S2CID 121448572. Archivado del original (PDF de la versión del informe técnico) el 26-11-2006 . Recuperado el 11-05-2007 .  
  29. ↑ Wilf, Herbert S. (1994). Generatingfunctionology (2.ª ed.). Boston, MA: Academic Press. p. 151. ISBN   978-0-12-751956-2. Zbl 0831.05001 . 
  30. ↑ Bousquet-Mélou, Mireille (1998). "Nuevos resultados enumerativos sobre animales dirigidos bidimensionales" . Matemáticas Discretas . 180 ( 1–3 ): 73–106 . doi : 10.1016/S0012-365X(97)00109-X .
  31. ↑ Delest, M.-P. (1988). "Funciones generadoras para poliominós convexos por columnas" . Journal of Combinatorial Theory, Series A. 48 ( 1): 12– 31. doi : 10.1016/0097-3165(88)90071-4 .
  32. ↑ Bousquet-Mélou, Mireille ; Fédou, Jean-Marc (1995). "La función generadora de poliominós convexos: la resolución de un sistema q -diferencial" . Matemáticas Discretas . 137 ( 1–3 ): 53–75 . doi : 10.1016/0012-365X(93)E0161-V .
  33. ^ Picciotto, Henri (1999), Laboratorios de geometría , MathEducationPage.org, p. 208 .
  34. ↑ Martin, George E. (1996). Polyominoes: A guide to puzzles and problems in tiling (2.ª ed.). Mathematical Association of America . ISBN  978-0-88385-501-0.
  35. ↑ CB Haselgrove; Jenifer Haselgrove (octubre de 1960). "Un programa informático para pentominós" (PDF) . Eureka . 23 : 16–18 .
  36. ↑ Golomb, Solomon W. (1970). "Tiling with Sets of Polyominoes" . Journal of Combinatorial Theory . 9 : 60–71 . doi : 10.1016/S0021-9800(70)80055-2 .
  37. ↑ ED Demaine; ML Demaine (junio de 2007). "Rompecabezas, emparejamiento de aristas y empaquetamiento de poliominos: conexiones y complejidad" . Graphs and Combinatorics . 23 : 195–208 . doi : 10.1007/s00373-007-0713-4 . S2CID 17190810 . 
  38. ↑ SW Golomb; LD Baumert (1965). "Backtrack Programming" . Journal of the ACM . 12 (4): 516– 524. doi : 10.1145/321296.321300 .
  39. ↑ Golomb, Poliominós , capítulo 8
  40. ↑ Reid, Michael. "Referencias para poliominós rectificables" . Archivado del original el 16 de enero de 2004. Consultado el 11 de mayo de 2007 .
  41. ↑ Reid, Michael. "Lista de rectángulos primos conocidos para varios poliominós" . Archivado del original el 16 de abril de 2007. Consultado el 11 de mayo de 2007 .
  42. ^ Klarner, DA; Göbel, F. (1969). "Cajas de embalaje con figuras congruentes". Indagaciones Mathematicae . 31 : 465–472 .
  43. ↑ Klarner, David A. (febrero de 1973). "Revisión de un teorema de base finita" (PDF) . Informe técnico de la Universidad de Stanford STAN-CS-73–338. Archivado del original (PDF) el 23 de octubre de 2007. Consultado el 12 de mayo de 2007 .
  44. ↑ Kamenetsky, Dmitry; Cooke, Tristrom (2015). "Tiling rectangles with holey polyominoes". arXiv : 1411.2699 [ cs.CG ].
  45. ↑ Golomb, Solomon W. (1966). "Tiling with Polyominoes" . Journal of Combinatorial Theory . 1 (2): 280– 296. doi : 10.1016/S0021-9800(66)80033-9 .
  46. ↑ Moore, Cristopher ; Robson, John Michael (2001). "Problemas difíciles de colocación de azulejos con azulejos simples" (PDF) . Archivado del original (PDF) el 17 de junio de 2013.
  47. ↑ Petersen, Ivars (25 de septiembre de 1999), "Math Trek: Tiling with Polyominoes" , Science News , archivado del original el 20 de marzo de 2008 , consultado el 11 de marzo de 2012..
  48. ↑ Gardner, Martin (julio de 1965). "Sobre la relación entre las matemáticas y los patrones ordenados del Op art". Scientific American . 213 (1): 100– 104. doi : 10.1038/scientificamerican1265-100 .
  49. ↑ Gardner, Martin (agosto de 1965). "Reflexiones sobre la tarea de comunicarse con organismos inteligentes de otros mundos". Scientific American . 213 (2): 96– 100. doi : 10.1038/scientificamerican0865-96 .
  50. ↑ Gardner, Martin (agosto de 1975). "Más sobre el recubrimiento del plano: las posibilidades de los poliominós, polidiamantes y polihexágonos". Scientific American . 233 (2): 112– 115. doi : 10.1038/scientificamerican0875-112 .
  51. ↑ Rawsthorne, Daniel A. (1988). "Complejidad de teselado de n -ominós pequeños ( n < 10)" . Matemáticas Discretas . 70 : 71–75 . doi : 10.1016/0012-365X(88)90081-7 .
  52. ↑ Rhoads, Glenn C. (2003). Planar Tilings and the Search for an Aperiodic Prototile . Tesis doctoral, Universidad de Rutgers.
  53. ↑ Grünbaum y Shephard, sección 9.4
  54. ↑ Keating, K.; Vince, A. (1999). "Teselado de poliominos isoédricos del plano" . Geometría discreta y computacional . 21 (4): 615– 630. doi : 10.1007/PL00009442 .
  55. ↑ Rhoads, Glenn C. (2005). "Teselaciones planas mediante poliominós, polihexágonos y polidiamantes" . Journal of Computational and Applied Mathematics . 174 (2): 329– 353. Bibcode : 2005JCoAM.174..329R . doi : 10.1016/j.cam.2004.05.002 .
  56. ^ Niţică, Viorel (2003). "Rep-tiles revisados". MASA selecta . Providence, RI: Sociedad Estadounidense de Matemáticas. págs. 205-217 . SEÑOR 2027179 .  
  57. ^ Mireles, JL, "Poly 2 ominós"
  58. ^ "Resta, G., "Polipoliominós"" . Archivado del original el 22-02-2011 . Recuperado el 02-07-2010 .
  59. ^ "Zucca, L., "Triple Pentominó"" . Consultado el 20 de abril de 2023 .
  60. ↑ Barbans, Uldis; Cibulis, Andris; Lee, Gilbert; Liu, Andy; Wainwright, Robert (2005). «Teoría de los números poliominós (III)». En Cipra, Barry Arthur ; Demaine, Erik D.; Demaine, Martin L.; Rodgers, Tom (eds.). Homenaje a un matemático erudito . Wellesley, MA: AK Peters. pp. 131–136 . ISBN  978-1-56881-204-5.
  61. ↑ Golomb, Solomon W. (1996-04-07). Polyominoes: Puzzles, Patterns, Problems, and Packings . Princeton University Press. p. 8. ISBN  978-0-691-02444-8.
  62. ↑ Etzion, Tuvi (28 de diciembre de 2020), «¿Rompecabezas y mosaicos ? Un fascinante reino de Salomón Golomb» , La sabiduría de Salomón , WORLD SCIENTIFIC, págs. 145-160 , doi : 10.1142/9789811234378_0013 , ISBN   978-981-12-3436-1, consultado el 21 de diciembre de 2025
  63. ↑ Diccionario Oxford de inglés , 2.ª edición, entrada dominó
  • Mosaicos de rectángulos finitos poliomino de Karl Dahlke
  • Implementación y descripción del método de Jensen.
  • Un documento que describe las estimaciones modernas (PS)
  • Weisstein, Eric W. "Poliomino" . MundoMatemático .
  • MathPages – Notas sobre la enumeración de poliominós con diversas simetrías
  • Lista de problemas de disección en Fairy Chess Review
  • Tétradas de Karl Scherer, Proyecto de Demostraciones de Wolfram .
Lecturas relacionadas
6 articulos
PentominoPentominoUn pentominó (o 5-omino ) es un poliomino de orden 5; es decir, un polígono plano formado por 5 cuadrados iguales unidos por sus aristas. El términ...FormaFormaUna forma es una representación gráfica de la forma de un objeto o de su límite externo, contorno o superficie externa . Se distingue de otras prop...Espacio conectadoSubespacios conexos y desconectados de R ² En topología y ramas relacionadas de las matemáticas , un espacio conexo es un espacio topológico que no...Unidad cuadradaEl cuadrado unitario en el plano real En matemáticas , un cuadrado unitario es un cuadrado cuyos lados tienen una longitud de 1. A menudo, el cuadr...PolyformPolyformEn matemáticas recreativas , una poliforma es una figura plana o un sólido compuesto construido mediante la unión de polígonos básicos idénticos . ...CuadradoEn geometría euclidiana , un cuadrado es un cuadrilátero regular , lo que significa que tiene cuatro lados rectos de igual longitud y cuatro ángulo...