🔢 mathematics

A Partition-Based Generating Function for Row-Convex Polyominoes

Este artículo propone una nueva función generadora basada en particiones que enumera los poliminós convexos por filas sin agujeros internos, vinculando las particiones enteras del área con las secuencias de longitudes de filas, y derivando así una fórmula exacta y estableciendo la tasa de crecimiento asintótico $S(N) \sim A2^N \cos(N\theta + \phi)$ .

Autores originales: Vincenzo M. Scarrica

Publicado 2026-05-06

📖 4 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Vincenzo M. Scarrica

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás construyendo una torre con bloques de Lego planos y rectangulares. Quieres apilarlos para crear una forma, pero tienes una regla muy específica: cada capa horizontal individual de tu torre debe ser una línea sólida e ininterrumpida de bloques. No puedes tener una capa que parezca una "U" o que tenga un hueco en el medio. En el mundo de las matemáticas, estas formas se llaman poliminós convexos por filas.

Este artículo de Vincenzo Scarrica es, esencialmente, un nuevo manual de instrucciones para contar cuántas torres diferentes puedes construir si estás limitado a usar exactamente $N$ bloques.

Aquí tienes el desglose de las ideas del artículo utilizando analogías simples:

1. La "receta" para una forma

Tradicionalmente, los matemáticos han tenido dificultades para contar estas formas porque son difíciles de organizar. Scarrica propone una nueva manera de pensar sobre ellas. En lugar de intentar dibujar cada forma posible, sugiere observar la receta de la forma.

Los ingredientes (particiones): Imagina que tienes 10 bloques. Puedes descomponerlos en capas de muchas maneras: una capa de 10, o 5+5, o 4+3+2+1, o 3+3+2+2, y así sucesivamente. En matemáticas, estas formas de descomponer un número en números más pequeños se llaman particiones enteras.
El ensamblaje (permutaciones): Una vez que decides una receta (por ejemplo, capas de 4, 3 y 2), puedes apilarlas en diferentes órdenes. Podrías poner el 4 en la base, o el 2 en la base. El artículo calcula cuántas formas únicas existen para ordenar estas capas.
El factor "inestabilidad" (desplazamientos): Esta es la parte ingeniosa. Cuando apilas una capa de 4 bloques sobre una capa de 3 bloques, no tienes que alinearlos perfectamente a la izquierda. Puedes deslizar la capa superior hacia la izquierda o hacia la derecha, siempre que al menos un bloque toque al que está debajo. El artículo calcula exactamente cuántas "posiciones de deslizamiento" son posibles para cada par de capas.

La fórmula: Para obtener el recuento total, el autor dice:

Toma cada forma posible de descomponer tu número total de bloques en capas.
Cuenta cuántas formas hay para ordenar esas capas.
Multiplica por el número de formas en que puedes deslizarlas juntas.
Suma todos esos resultados.

2. El truco del "espejo"

El artículo también pregunta: "¿Qué pasa si damos la vuelta a la torre?".
Si construyes una forma y luego miras su reflejo en un espejo, ¿es una forma nueva o la misma?

Si la forma es perfectamente simétrica (como una pirámide), darle la vuelta no la cambia.
Si está desequilibrada, la imagen en el espejo es una forma diferente.
El autor proporciona una manera de estimar cuántas formas únicas existen si decidimos que una forma y su imagen en el espejo cuentan como una sola cosa. Esto ayuda a simplificar el proceso de conteo, aunque el artículo señala que es un poco complicado hacerlo perfectamente.

3. El resultado del "número mágico"

Después de realizar todo este conteo complejo, el artículo deriva una "fórmula mágica" (una función generadora) que predice cómo crece el número de formas a medida que añades más bloques.

El crecimiento: El número de formas no crece lentamente; explota exponencialmente.
El patrón: El crecimiento sigue un patrón similar a una ola que se hace cada vez más grande. El artículo calcula que para un número grande de bloques ( $N$ ), el número de formas es aproximadamente proporcional a $2^N$ (duplicándose cada vez que añades un bloque, con una ligera oscilación).
La "oscilación": El crecimiento no es una línea recta; oscila (sube y baja ligeramente) basándose en un ángulo específico relacionado con el número $\sqrt{7}$ .

4. Lo que esto puede y no puede hacer

El artículo es muy claro sobre sus límites:

Para qué funciona: Funciona perfectamente para formas donde cada fila es un bloque sólido (convexas por filas).
En lo que falla: No puede contar fácilmente formas "cóncavas" (formas con agujeros o huecos en las filas). Imagina intentar construir una torre donde una capa tiene un hueco en el medio, como un puente. Las matemáticas se vuelven demasiado desordenadas porque las reglas de "deslizamiento" se vuelven increíblemente complicadas cuando las piezas no están conectadas. El artículo admite que extender este método a esas formas desordenadas es actualmente demasiado difícil.

Resumen

En resumen, este artículo ofrece una nueva y más sencilla manera de contar tipos específicos de formas bloquosas tratándolas como recetas hechas de números. Confirma que el número de estas formas crece muy rápido (duplicándose con cada bloque añadido) y proporciona una herramienta matemática precisa para predecir exactamente cuántas habrá, coincidiendo con resultados famosos anteriores en el campo.

Resumen Técnico: Una Función Generadora Basada en Particiones para Poliominos Convexos por Filas

Planteamiento del Problema
La enumeración de poliominos —conjuntos finitos de cuadrados unitarios conectados en una red entera bidimensional— sigue siendo un problema desafiante en combinatoria, particularmente para clases definidas por restricciones geométricas. Aunque las fórmulas de forma cerrada para poliominos generales son en gran medida desconocidas, se han estudiado extensamente subclases específicas como los poliominos convexos, convexos por filas y convexos por columnas. Los métodos existentes, notablemente los de Klarner y Hickerson, dependen de relaciones de recurrencia y argumentos de matriz de transferencia para derivar funciones generadoras. Sin embargo, las fórmulas de forma cerrada explícitas para contar poliominos convexos sin agujeros internos siguen siendo limitadas. Este trabajo aborda la enumeración de poliominos convexos por filas (donde cada fila consiste en una secuencia contigua de celdas) sin agujeros internos, buscando un enfoque combinatorio alternativo que vincule la enumeración de poliominos directamente con las particiones de enteros.

Metodología
El método propuesto establece una correspondencia directa entre los poliominos convexos por filas y las particiones de enteros del área total $N$ . La lógica central procede de la siguiente manera:

Descomposición por Particiones: Cada poliomino convexo por filas de área $N$ se descompone en una secuencia de longitudes de fila $(\lambda_1, \lambda_2, \dots, \lambda_k)$ tal que $\sum \lambda_i = N$ . Esta secuencia forma una partición de enteros de $N$ .
Alineación Horizontal (Desplazamientos): Para una secuencia fija de longitudes de fila, el número de alineaciones horizontales válidas está determinado por el "desplazamiento" entre filas consecutivas. Si la fila $i$ tiene longitud $L_i$ y la fila $i+1$ tiene longitud $L_{i+1}$ , el número de posiciones donde pueden tocarse (asegurando la 4-conectividad) es $L_i + L_{i+1} - 1$ . El número total de configuraciones para una secuencia ordenada fija es el producto de estos factores de desplazamiento: $\prod_{i=1}^{k-1} (\lambda_i + \lambda_{i+1} - 1)$ .
Factor de Permutación: Dado que el orden de las filas importa para la forma del poliomino, el método cuenta las permutaciones distintas de las partes de la partición. Se introduce un factor $\Phi(\lambda)$ para contar el número de permutaciones distintas de la partición $\lambda$ , ajustando por tamaños de partes repetidos (multiplicidades).
Fórmula de Enumeración: El número total de poliominos convexos por filas de tamaño $N$ , denotado $S(N)$ , se obtiene sumando el producto del factor de permutación y el producto de desplazamientos sobre todas las particiones de enteros de $N$ :
$S(N) = \sum_{\lambda \in P(N)} \Phi(\lambda) \prod_{i=1}^{\ell(\lambda)-1} (\lambda_i + \lambda_{i+1} - 1)$
Derivación de la Función Generadora: El trabajo traduce esta suma combinatoria en una función generadora $G(x) = \sum S(N)x^N$ . Al modelar el problema como una serie de transferencia de composiciones ordenadas y resolver el sistema resultante de ecuaciones lineales, se deriva la función generadora racional exacta.

Resultados Clave

Función Generadora Exacta: El trabajo deriva la función generadora para poliominos convexos por filas como:
$G(x) = \frac{x(1-x)^3}{1 - 5x + 7x^2 - 4x^3}$
Este resultado se muestra que coincide exactamente con la función generadora para poliominos convexos por columnas derivada previamente por Klarner y Hickerson, validando el enfoque basado en particiones.
Crecimiento Asintótico: El análisis de los polos de $G(x)$ revela el comportamiento asintótico de la secuencia. Las singularidades dominantes son polos complejos conjugados en $x = \frac{3 \pm i\sqrt{7}}{8}$ , con módulo $1/2$ . En consecuencia, el número de poliominos crece como:
$S(N) \sim A \cdot 2^N \cos(N\theta + \phi)$
donde $\theta = \arctan(\sqrt{7}/3)$ . Esto indica un crecimiento puramente exponencial con una base de 2, en contraste con el crecimiento subexponencial de las particiones de enteros sin restricciones.
Verificación Numérica: La fórmula se implementó en Python (Algoritmo 1) y se verificó contra valores conocidos de la secuencia A001169 de la OEIS para $N$ hasta 12, mostrando un acuerdo perfecto.
Reducción por Simetría: El trabajo discute límites para reducir el conteo identificando configuraciones de imagen especular, señalando que, aunque es posible un ajuste exacto de la mitad para casos específicos de paridad, una reducción de forma cerrada general para poliominos simétricos es difícil de derivar directamente de la fórmula de particiones.

Significado y Limitaciones
La contribución principal de este trabajo es el establecimiento de un vínculo combinatorio directo entre las particiones de enteros y la enumeración de poliominos convexos por filas. Al reformular el problema en términos de particiones y sus permutaciones, el trabajo ofrece un "marco simple pero efectivo" tanto para la enumeración exacta como para el análisis asintótico sin depender de los argumentos de matriz de transferencia más complejos utilizados tradicionalmente.

El trabajo señala explícitamente las limitaciones de este enfoque: se aplica estrictamente a poliominos convexos por filas sin agujeros internos. Se considera que extender el método a poliominos cóncavos es combinatoriamente intratable porque las filas cóncavas pueden dividirse en múltiples componentes desconectados (sub-particiones) con espacios variables, haciendo que la imposición de la restricción de 4-conectividad sea significativamente más compleja.

El trabajo se posiciona como una alternativa a los métodos clásicos (Klarner, Hickerson) en lugar de un reemplazo, proporcionando una nueva perspectiva que simplifica la derivación de la función generadora y las estimaciones asintóticas para esta clase específica de poliominos. Las aplicaciones potenciales mencionadas incluyen priores de forma en el análisis de imágenes discretas, modelado basado en cuadrículas y generación procedural, aunque estas se presentan como contextos donde dicha enumeración es relevante, más que como resultados experimentales de este estudio específico.