We consider colored compositions where only some parts are allowed different colors, depending on their locations in the composition. The counting sequences are obtained through generating functions. Connections to many other combinatorial objects are discussed, with combinatorial arguments provided and generalized for these observations.
- ID del Artículo: 2511.08529
- Título: Combinatoria de composiciones coloreadas posicionales
- Autores: Andrew Li (Universidad de Princeton), Hua Wang (Universidad de Georgia Southern)
- Clasificación: math.CO (Combinatoria)
- Fecha de Publicación: 11 de noviembre de 2025 (preimpresión en arXiv)
- Enlace del Artículo: https://arxiv.org/abs/2511.08529
- Palabras Clave: composiciones enteras, composiciones coloreadas, pruebas combinatorias
- Clasificación MSC: 05A17, 11B37
Este artículo estudia composiciones coloreadas posicionales (positional colored compositions), es decir, composiciones enteras donde se permite colorear solo las partes en posiciones específicas dentro de la composición. Los autores obtienen secuencias de conteo mediante funciones generatrices y descubren conexiones profundas entre estas secuencias y diversos objetos combinatorios, proporcionando pruebas biyectivas y generalizaciones para estas conexiones.
El problema central que estudia este artículo es: cómo contar composiciones enteras cuando solo las partes en posiciones específicas pueden ser n-coloreadas, y cuál es la relación de estas estructuras con otros objetos combinatorios.
- Significado Teórico: Las composiciones enteras son objetos fundamentales en matemática combinatoria. Las composiciones n-coloreadas han sido ampliamente estudiadas desde su introducción por Agarwal en 2000. Las composiciones coloreadas posicionales, como una nueva variante, enriquecen este campo de investigación.
- Conectividad: A través de la investigación, se descubre que las composiciones coloreadas posicionales son equivalentes a composiciones con colores restringidos, composiciones (n choose 2)-coloreadas, cadenas ternarias, cadenas binarias, permutaciones separables que evitan 321, entre otros objetos combinatorios, revelando conexiones profundas entre diferentes estructuras combinatorias.
- Valor Metodológico: Mediante funciones generatrices y pruebas biyectivas, proporciona nuevas herramientas y perspectivas para el conteo combinatorio.
- La investigación existente se enfoca principalmente en composiciones donde todas las partes están coloreadas o donde se restringen colores específicos
- Falta un estudio sistemático de reglas de coloración basadas en posiciones
- Las relaciones de equivalencia entre diferentes objetos combinatorios aún no han sido suficientemente exploradas
Los autores descubren coincidencias en ciertas secuencias de conteo a través de OEIS (Enciclopedia en Línea de Secuencias de Números Enteros), lo que los lleva a explorar las conexiones intrínsecas entre composiciones coloreadas posicionales y otras estructuras combinatorias, proporcionando comprensión profunda mediante argumentos combinatorios.
- Introducción del Concepto de Composiciones Coloreadas Posicionales: Se define la composición (m,k)-n-coloreada, donde las partes en posiciones k (mod m) se colorean con n colores, mientras que las otras partes no se colorean.
- Derivación de Funciones Generatrices:
- Se proporciona la función generatriz para composiciones coloreadas EVEN (posiciones pares)
- Se proporciona la función generatriz para composiciones coloreadas ODD (posiciones impares)
- Se proporciona la función generatriz para composiciones (m,k)-n-coloreadas generales
- Establecimiento de Múltiples Relaciones Biyectivas:
- Composiciones coloreadas EVEN con composiciones n-coloreadas con colores restringidos a 2
- Composiciones coloreadas ODD con composiciones (n choose 2)-coloreadas
- Composiciones coloreadas EVEN con cadenas ternarias específicas
- Composiciones coloreadas EVEN con sumas de productos de runs en cadenas binarias
- Composiciones coloreadas EVEN con permutaciones separables que evitan 321
- Proporcionar Pruebas Biyectivas de Identidades Combinatorias: Se demuestran identidades como e(k+1) = e(k) + o(k) y se generalizan a casos generales.
- Descubrimiento de Nuevas Relaciones de Equivalencia Combinatoria: Se revelan conexiones profundas entre objetos combinatorios aparentemente no relacionados.
Conceptos Básicos:
- Composición (composition): Suma ordenada de enteros positivos. Por ejemplo, las composiciones de 3 son: 1+1+1, 1+2, 2+1, 3
- Composición n-coloreada: Cada parte de tamaño k en la composición puede elegir un color de 1 a k, indicado con un subíndice
- Composición (m,k)-n-coloreada: Las partes en posiciones k (mod m) se colorean con n colores, mientras que otras partes no se colorean
Casos Especiales:
- Composición coloreada EVEN: Composición (2,0)-n-coloreada, es decir, coloración en posiciones pares
- Composición coloreada ODD: Composición (2,1)-n-coloreada, es decir, coloración en posiciones impares
- Función generatriz para partes sin coloración:
x+x2+x3+⋯=1−xx
- Función generatriz para partes n-coloreadas:
x+2x2+3x3+⋯=(1−x)2x
Esto es porque una parte de tamaño k tiene k opciones de color.
Se consideran dos casos:
- Número impar de partes: Al menos una parte sin coloración, seguida de cualquier número de pares (parte coloreada + parte sin coloración)
1−xx∑i=0∞((1−x)3x2)i=(1−x)3−x2x(1−x)2
- Número par de partes: Pares positivos (parte coloreada + parte sin coloración)
∑i=1∞((1−x)3x2)i=(1−x)3−x2x2
Función generatriz total:
Fe(x)=−x3+2x2−3x+1x3−x2+x
Corresponde a la secuencia OEIS A034943.
Análisis similar produce la función generatriz:
Fo(x)=−x3+2x2−3x+1x
Corresponde a la secuencia OEIS A095263.
Se analizan tres casos según el número de partes módulo m:
- 0 (mod m): Cada m partes contienen 1 coloreada y m-1 sin coloración
- j (mod m), 1≤j≤k-1: j partes sin coloración más el caso 1
- ℓ (mod m), k≤ℓ≤m-1: ℓ-1 partes sin coloración + 1 parte coloreada más el caso 1
La innovación técnica central del artículo radica en la construcción de múltiples biyecciones ingeniosas.
Dirección de Mapeo 1 (Color restringido 2 → EVEN coloreada):
- Procesar cada parte de izquierda a derecha
- Para una parte coloreada p_c en posición impar (c≥3), descomponer como: (c-2) + (p-c+2)_2
- Partes en posición impar con color 1 pierden el color
Mapeo Inverso:
- Para una parte con color 2 en posición par q_2, fusionar con la parte anterior p para obtener (p+q)_{p+2}
Ejemplo: 3_3, 1_1, 6_4, 4_4 → 1, 2_2, 1, 6_4, 2, 2_2
Esta es la biyección entre composiciones coloreadas ODD y composiciones (n choose 2)-coloreadas (cada parte tiene dos spots diferentes).
Mapeo (ODD coloreada → (n choose 2)-coloreada):
- Número par de partes: Fusionar cada dos tiles adyacentes en un tile, manteniendo posiciones de spots, extender el último tile con una unidad sin spot
- Número impar de partes: Primero añadir una unidad con spot al final, luego ejecutar la operación anterior
Mapeo Inverso: Cortar cada tile antes del segundo spot, eliminar la última unidad.
Composiciones coloreadas EVEN ↔ Cadenas ternarias con dígitos consecutivos restringidos, que no comienzan con 2 y no terminan con 0
Reglas de Mapeo (basadas en representación de spotted tiling):
- Línea dentro del tile → 1
- Línea antes del spot → 0
- Línea después del spot → 2
- Línea al final de parte en posición impar → 1
Restricciones Garantizadas:
- Después de 0 solo puede haber 0 o 2
- Después de 1 solo puede haber 1 o 0
- No puede comenzar con 2 (0 debe estar antes del primer 2)
- No puede terminar con 0
El número de composiciones coloreadas EVEN(k) = Suma de productos de longitudes de runs de 1 en todas las cadenas binarias de longitud k
Mapeo:
- Añadir 0 al inicio de la cadena binaria
- Subcadenas consecutivas de 0s o 1s se mapean a partes de tamaño correspondiente
- Subcadena de 0s → parte en posición impar (sin coloración)
- Subcadena de 1s → parte en posición par (coloreada)
- Cada composición coloreada EVEN corresponde a un número de opciones de color = producto de tamaños de partes en posiciones pares
Utiliza estructura de árbol binario etiquetado:
Mapeo (Permutación → Composición coloreada EVEN):
- Para cada nodo negativo: a hojas del subárbol izquierdo + b hojas del subárbol derecho → parte coloreada (a+b-1)_a (posición par)
- c hojas recursivas consecutivas entre nodos negativos → parte sin coloración c+1 (posición impar)
Mapeo Inverso:
- Parte sin coloración menos 1 → número de hojas entre nodos negativos
- Parte coloreada más 1 y distribución según color → distribución de hojas bajo nodo negativo
Este artículo es un trabajo de matemática combinatoria pura sin experimentos en sentido tradicional. Los métodos de validación incluyen:
- Validación de Secuencias OEIS: Verificación mediante la base de datos OEIS de secuencias de conteo
- A034943: Composiciones coloreadas EVEN
- A095263: Composiciones coloreadas ODD
- Validación por Enumeración a Pequeña Escala: Verificación de fórmulas mediante enumeración manual de casos para enteros pequeños
- Corrección de Biyecciones: Demostración del proceso de construcción de biyecciones mediante ejemplos concretos
- Teoría de funciones generatrices
- Método de prueba biyectiva
- Representación visual de spotted tiling
Los "resultados" del artículo se manifiestan en las relaciones de equivalencia establecidas:
- Teorema 3.1: Composiciones coloreadas EVEN ≡ Composiciones n-coloreadas con color restringido 2
- Proporciona biyección constructiva basada en spotted tiling
- Teorema 3.2: Composiciones coloreadas ODD(k) ≡ Composiciones (n choose 2)-coloreadas(k+1)
- Explica la relación de secuencias observada en OEIS
- Corolario 1: Composiciones coloreadas ODD(k) ≡ Cadenas ternarias de longitud k-1 que evitan 01 y 12
- Establece indirectamente conexión con la literatura 3
- Teorema 3.3: Composiciones coloreadas EVEN(k) ≡ Cadenas ternarias específicas de longitud k con dígitos consecutivos restringidos
- Teorema 3.4: Composiciones coloreadas EVEN(k+1) = Σ(producto de longitudes de runs de 1 en cadenas binarias de longitud k)
- Teorema 3.5: Composiciones coloreadas ODD(k) = Σ(producto de longitudes de runs de 1 en cadenas binarias de longitud k que comienzan con 1)
- Teorema 3.7: Composiciones coloreadas EVEN(k) ≡ Permutaciones separables que evitan 321 en k
Teorema 3.6: Para cualquier k≥1, ℓ≥2, 1≤m≤ℓ-1:
cm,k+1(ℓ+1)=cm,k+1(ℓ)+cm,k(ℓ)
Prueba Combinatoria del caso especial e(k+1) = e(k) + o(k):
- Composiciones coloreadas EVEN(k+1) con primera parte igual a 1 → Eliminando se obtiene composición coloreada ODD(k)
- Composiciones coloreadas EVEN(k+1) con primera parte > 1 → Restando 1 se obtiene composición coloreada EVEN(k)
- Esto proporciona una biyección a una unión disjunta
Ejemplo 1 (Teorema 3.1):
- Color restringido 2: 3_3, 1_1, 6_4, 4_4
- Proceso de mapeo: 3_3 se descompone en 1+2_2; 1_1 se mantiene; 6_4 se mantiene; 4_4 se descompone en 2+2_2
- Resultado: 1, 2_2, 1, 6_4, 2, 2_2 (EVEN coloreada)
Ejemplo 2 (Teorema 3.2):
- ODD coloreada: 4_2 + 3_1 + 5_4 + 2_1 + 1_1 = 15
- Mapeo a (n choose 2)-coloreada: 7_{2,5} + 7_{4,6} + 2_{1,2} = 16
Ejemplo 3 (Teorema 3.3):
- EVEN coloreada: 1 + 2_i + 1 + 6_j + 4 (i∈{1,2}, j∈{1,...,6})
- Mapeo a cadena ternaria: 00200002221111
Ejemplo 4 (Teorema 3.7):
- Permutación separable que evita 321: (1,2,6,7,3,4,5,8,9,10,12,13,11)
- Mapeo mediante representación de árbol binario a: 3 + 4_2 + 4 + 2_2
- Marco Unificado: Las composiciones coloreadas posicionales proporcionan un marco de conteo unificado para múltiples objetos combinatorios aparentemente no relacionados
- Poder de Funciones Generatrices: Mediante análisis de funciones generatrices, se pueden manejar sistemáticamente reglas de coloración dependientes de posición
- Naturaleza Constructiva de Biyecciones: Todas las biyecciones son constructivas, proporcionando algoritmos explícitos para transformación entre objetos
- Importancia de Visualización: La representación de spotted tiling juega un papel clave en la construcción de biyecciones
- Agarwal (2000)1: Introducción del concepto de composiciones n-coloreadas
- Hopkins (2012)6: Introducción del método de representación de spotted tiling
- Hopkins & Wang (2021)2: Estudio de composiciones n-coloreadas con colores restringidos
- Acosta et al. (2019)4: Estudio de nuevas funciones de composiciones n-coloreadas restringidas
- Dedrickson (2012)3: Estudio de biyección entre composiciones (n choose 2)-coloreadas y cadenas ternarias
- Agarwal & Narang (2008)11: Conexión entre composiciones n-coloreadas y caminos de red
- Collins et al. (2013)10: Relación entre palabras binarias y composiciones n-coloreadas
- Gibson et al. (2018)5: Composiciones n-coloreadas cíclicas
- Narang & Agarwal (2006)8, Guo (2010)9: Composiciones n-coloreadas palíndrómicas
- Coloración Dependiente de Posición: Primer estudio sistemático de reglas de coloración basadas en posición
- Nuevas Biyecciones: Las biyecciones con permutaciones separables que evitan 321 y cadenas ternarias específicas son nuevas
- Perspectiva Unificada: Incorpora múltiples resultados conocidos en un marco unificado
- Contribuciones Teóricas:
- Definición y estudio de composiciones coloreadas posicionales como nuevo objeto combinatorio
- Obtención de fórmulas de conteo exactas mediante funciones generatrices
- Establecimiento de relaciones de equivalencia con al menos 6 clases de otros objetos combinatorios
- Contribuciones Metodológicas:
- Demostración de la efectividad de funciones generatrices en el manejo de reglas dependientes de posición
- Proporciona múltiples construcciones biyectivas ingeniosas, enriqueciendo técnicas de prueba combinatoria
- La representación de spotted tiling se demuestra como herramienta poderosa de visualización y construcción
- Descubrimientos de Conectividad:
- Revelación de conexiones profundas entre composiciones con colores restringidos, composiciones (n choose 2)-coloreadas, cadenas ternarias, runs de cadenas binarias, permutaciones separables y otros objetos
- Estas conexiones no son solo equivalencias de conteo, sino que tienen construcciones biyectivas explícitas
- Exploración Incompleta de Casos Generales:
- La sección 2.3 proporciona funciones generatrices para composiciones (m,k)-n-coloreadas generales, pero las conexiones con otros objetos combinatorios se limitan al caso m=2
- Las interpretaciones combinatorias para valores generales de m aún requieren investigación
- Indirectividad de Algunas Pruebas:
- El Corolario 1 (composiciones coloreadas ODD con cadenas ternarias) se obtiene indirectamente mediante el Teorema 3.2 y la literatura 3
- Una prueba combinatoria directa podría proporcionar mayor profundidad de comprensión
- Sistematicidad de Generalizaciones:
- Aunque se proporciona la generalización del Teorema 3.6, las generalizaciones de otros resultados no son sistemáticas
- Esto limita el alcance de la teoría
- Complejidad Computacional:
- No se discute la complejidad algorítmica de generación y enumeración de estos objetos
- No se analiza la eficiencia computacional de las biyecciones
La sección 4 del artículo propone explícitamente:
- Interpretaciones Combinatorias de Composiciones Coloreadas Posicionales Generales:
- Investigar conexiones entre composiciones (m,k)-n-coloreadas y otros objetos combinatorios
- Buscar biyecciones para valores generales de m y k
- Prueba Directa del Corolario 1:
- Construir biyección directa entre composiciones coloreadas ODD y cadenas ternarias que evitan 01 y 12
- Generalizar este resultado a otros casos
- Composiciones Coloreadas Posicionales con Colores Restringidos:
- Combinar ideas de la sección 3.1, investigar composiciones coloreadas posicionales con restricciones de color específicas
- Explorar propiedades interesantes de estas clases
- Otras Reglas de Posición:
- Considerar reglas de coloración más complejas dependientes de posición
- Por ejemplo: coloración que dependa tanto del tamaño como de la posición de la parte
- Aspectos Algorítmicos y Computacionales:
- Desarrollar algoritmos eficientes de generación y enumeración
- Investigar métodos de muestreo aleatorio
- Innovación Conceptual Fuerte:
- Las composiciones coloreadas posicionales son una generalización natural y significativa
- Unifican múltiples objetos combinatorios conocidos
- Abren nuevas direcciones de investigación
- Rigor Técnico Elevado:
- Derivaciones de funciones generatrices claras y completas
- Construcciones biyectivas detalladas y verificables
- Todos los resultados principales tienen pruebas rigurosas
- Construcciones Biyectivas Ingeniosas:
- La biyección con permutaciones separables que evitan 321 (Teorema 3.7) es particularmente ingeniosa, utilizando estructura de árbol binario
- La biyección con cadenas ternarias (Teorema 3.3) es elegante, utilizando elegantemente la partición de líneas en la representación de spotted tiling
- La conexión con runs de cadenas binarias (Teorema 3.4) revela principios de conteo profundos
- Calidad de Visualización:
- La representación de spotted tiling es intuitiva y clara
- Las figuras (como Figuras 2-6) apoyan efectivamente la comprensión
- Los ejemplos están bien seleccionados, cubriendo casos clave
- Riqueza de Conectividad:
- Establece relaciones de equivalencia con 6 clases diferentes de objetos combinatorios
- Cada conexión tiene significado combinatorio
- Proporciona múltiples puntos de entrada para investigación futura
- Claridad de Escritura Elevada:
- Estructura organizacional razonable, de lo especial a lo general
- Definiciones claras, notación consistente
- Líneas de prueba claras, fáciles de seguir
- Incompletitud de Generalizaciones:
- Falta interpretación combinatoria para casos (m,k) generales
- La fórmula de función generatriz en la sección 2.3 no se utiliza suficientemente
- Esto limita la completitud de la teoría
- Indirectividad de Algunas Pruebas:
- El Corolario 1 depende del resultado de la literatura 3
- Una construcción directa podría ser más inspiradora
- Este es un defecto que los autores reconocen en la sección 4
- Ausencia de Aspectos Computacionales:
- No se discute complejidad algorítmica
- No se proporcionan implementaciones o código
- Valor limitado para aplicaciones prácticas
- Comparación Insuficiente con Trabajo Existente:
- Aunque se citan referencias relevantes, la comparación detallada de métodos y resultados es limitada
- Las ventajas del método del artículo sobre métodos existentes no se exponen suficientemente
- Escenarios de Aplicación Poco Claros:
- Como trabajo puramente teórico, no se discuten aplicaciones prácticas
- El significado práctico de composiciones coloreadas posicionales no se explora
- Esto puede limitar el interés de los lectores
- Algunos Detalles de Prueba Podrían Ser Más Detallados:
- Por ejemplo, el mapeo inverso del Teorema 3.7 sobre cómo recuperar la permutación completa a partir de tamaños de partes carece de detalle
- La inyectividad y sobreyectividad de las biyecciones a veces requieren verificación por parte del lector
- Valor Teórico Elevado:
- Contribuye una nueva variante a la teoría de composiciones enteras
- Revela conexiones profundas entre múltiples objetos combinatorios
- Los métodos de función generatriz y biyección tienen valor demostrativo
- Contribución Metodológica:
- Demuestra cómo estudiar sistemáticamente estructuras combinatorias con reglas dependientes de posición
- El uso de spotted tiling proporciona herramienta para otros problemas
- Las técnicas de construcción biyectiva pueden inspirar investigación similar
- Potencial de Investigación Posterior Grande:
- Los múltiples problemas abiertos propuestos en la sección 4 merecen exploración
- Puede generalizarse a otros tipos de objetos combinatorios
- Puede producir conexiones con otros campos matemáticos (álgebra, topología)
- Reproducibilidad Fuerte:
- Todas las construcciones son algoritmos explícitos
- Las funciones generatrices pueden usarse para verificación computacional
- Las secuencias OEIS proporcionan vía de verificación independiente
- Valor Educativo:
- Apropiado como material complementario para cursos de matemática combinatoria
- Demuestra el poder de funciones generatrices y pruebas biyectivas
- Ejemplos abundantes, adecuados para aprendizaje
- Investigación en Matemática Combinatoria:
- Investigadores de composiciones enteras y sus variantes
- Investigadores de teoría de funciones generatrices
- Investigadores de combinatoria biyectiva
- Campos Relacionados:
- Investigación de permutaciones separables (relacionada con Teorema 3.7)
- Combinatoria de cadenas (relacionada con Teoremas 3.3, 3.4)
- Teoría de caminos de red y tilings
- Aplicaciones Educativas:
- Estudios de caso para cursos de matemática combinatoria
- Ejemplos de enseñanza de métodos de función generatriz
- Entrenamiento de técnicas de prueba biyectiva
- Aplicaciones Potenciales (requieren investigación adicional):
- Teoría de codificación (mediante conexión con cadenas)
- Análisis de algoritmos (mediante conexión con permutaciones)
- Teoría de probabilidad (propiedades aleatorias de estructuras combinatorias)
1 A.K. Agarwal, "n-colour compositions", Indian J. Pure Appl. Math. 31(2000) 1421–1437.
- Trabajo fundacional que introduce el concepto de composiciones n-coloreadas
2 B. Hopkins, H. Wang, "Restricted Color n-color Compositions", Journal of Combinatorics, 12 (2021), 355-377.
- Estudia composiciones con colores restringidos, directamente relacionado con Teorema 3.1 del artículo
3 C. Dedrickson, "Compositions, Bijections, and Enumerations" (2012), Electronic Theses and Dissertations. 17.
- Establece biyección entre composiciones (n choose 2)-coloreadas y cadenas ternarias, base del Corolario 1
6 B. Hopkins, "Spotted tilings and n-color compositions", Integers 12B (2012) Article A6
- Introduce representación de spotted tiling, herramienta de visualización central del artículo
Este es un artículo de teoría combinatoria de alta calidad con las siguientes características destacadas:
- Innovación: Introduce composiciones coloreadas posicionales como concepto nuevo, proporcionando generalización valiosa a la teoría de composiciones enteras.
- Profundidad: No solo proporciona fórmulas de conteo, sino que más importantemente establece conexiones profundas con múltiples objetos combinatorios, cada conexión con prueba biyectiva rigurosa.
- Completitud: De definiciones, funciones generatrices, casos especiales a casos generales, y conexiones con otros objetos, la estructura lógica es completa.
- Técnica: Las derivaciones de funciones generatrices y construcciones biyectivas demuestran fundamentos sólidos en matemática combinatoria del autor.
- Inspiración: Proporciona múltiples direcciones claras para investigación posterior, con fuerte continuidad.
Direcciones de Mejora Sugeridas:
- Complementar con interpretaciones combinatorias para casos (m,k) generales
- Proporcionar prueba directa del Corolario 1
- Aumentar discusión de aspectos algorítmicos y computacionales
- Explorar escenarios de aplicación práctica
En general, este es un artículo excelente digno de publicación, con contribución sustancial al campo de la matemática combinatoria, particularmente recomendado para investigadores interesados en composiciones enteras, funciones generatrices y pruebas biyectivas.