Pattern Avoidance for Fibonacci Sequences using $k$-Regular Words

Este artículo presenta una demostración simple de que la recurrencia $a_k(n)$ cuenta las palabras $k$-regulares que evitan ciertos patrones, complementa el resultado probando que $b_k(n)$ cuenta las que evitan otros patrones específicos, y conjetura una relación cuadrática con los números de Fibonacci para un caso vinculado.

Lo esencial

¡Hola! Imagina que las matemáticas son como un inmenso laboratorio de cocina. En este laboratorio, los matemáticos no cocinan pasteles, sino que "cocinan" palabras siguiendo reglas muy estrictas.

Este artículo es como un nuevo libro de recetas que descubre cómo ciertas "sopas de letras" siguen patrones numéricos famosos, como la secuencia de Fibonacci (esa famosa sucesión 1, 1, 2, 3, 5, 8...).

Aquí te explico los conceptos clave de forma sencilla, usando analogías:

1. Los Ingredientes: Las "Palabras k-regulares"

Imagina que tienes un set de letras: 1, 2, 3... hasta la letra n.

• Una palabra k-regular es como una receta donde cada letra debe aparecer exactamente k veces.
• Si k=1, es como una lista de compras donde cada ítem aparece una vez (una permutación normal).
• Si k=2, es como tener dos pares de zapatos para cada número: dos 1s, dos 2s, dos 3s, etc.
• Si k=3, tienes tres de cada uno.

El reto de los autores es: ¿De cuántas formas diferentes podemos ordenar estas letras sin cometer "errores de cocina"?

2. Los "Errores de Cocina" (Patrones Prohibidos)

En este juego, hay ciertas combinaciones de letras que están prohibidas porque arruinan el sabor de la sopa. A estas las llaman patrones.

• Por ejemplo, el patrón 121 significa: "No puedes tener un número pequeño, luego uno grande, y luego volver al pequeño" (como ir a la tienda, comprar algo caro, y luego volver a comprar algo barato inmediatamente después).
• El patrón 123 sería: "No puedes subir de precio tres veces seguidas".

Los autores se preguntan: Si prohíbo ciertas combinaciones, ¿cuántas recetas válidas puedo hacer?

3. El Gran Descubrimiento: Dos Nuevas Recetas

El artículo presenta dos familias principales de recetas que siguen dos tipos de secuencias matemáticas famosas:

A. La Secuencia "Fibonacci-k" (Receta 1)

Imagina que quieres cocinar usando k copias de cada número, pero prohíbes cuatro patrones específicos (121, 123, 132, 213).

• La magia: El número de recetas válidas que puedes hacer sigue una regla muy simple:
  • Número de recetas hoy = (Recetas de ayer) + k × (Recetas de anteayer).
• La analogía: Es como si cada día pudieras hacer lo que hiciste ayer, o bien, tomar lo que hiciste hace dos días y multiplicarlo por k (porque tienes k opciones de ingredientes extra).
• Ejemplo: Si k=2 (dos de cada número), la secuencia es 1, 1, 3, 5, 11... ¡Esta es la famosa secuencia de Jacobsthal! Si k=1, recuperamos la secuencia de Fibonacci clásica.

B. La Secuencia "k-Fibonacci" (Receta 2)

Aquí cambian las reglas prohibidas. Ahora solo prohíben dos patrones (122 y 213).

• La magia: El número de recetas sigue otra regla:
  • Número de recetas hoy = k × (Recetas de ayer) + (Recetas de anteayer).
• La diferencia: Aquí, lo que hiciste ayer se multiplica por k (tienes muchas formas de expandirlo), y añades lo que hiciste hace dos días.
• Resultado: Esto genera una nueva familia de números que generaliza la secuencia de Fibonacci.

4. El "Super-Poder" Vincular (La Receta Cuadrada)

En la última parte, los autores hacen algo muy interesante. Toman la primera receta (la de Fibonacci-k) y le ponen una regla extra: los ingredientes prohibidos deben estar pegados.

• Imagina que el patrón prohibido "121" no solo está mal si aparece separado, sino que solo está mal si los números están uno al lado del otro.
• El resultado sorprendente: Al hacer esto, el número de recetas válidas deja de ser la secuencia de Jacobsthal y se convierte en el cuadrado de la secuencia de Fibonacci (1, 1, 4, 9, 25...).
• La analogía: Es como si al poner una "cinta adhesiva" sobre las reglas prohibidas, la cantidad de formas de cocinar se disparara al cuadrado.

¿Por qué es importante esto?

Antes, los matemáticos sabían cómo contar estas recetas para casos muy simples (como cuando k=1, que son solo permutaciones normales).

• Lo que hacen estos autores: Han encontrado una forma simple y directa de demostrar que estas reglas funcionan para cualquier cantidad de copias (k).
• Han creado un "puente" entre dos mundos: el de las palabras repetidas (k-regulares) y las secuencias numéricas famosas.

En resumen

Este artículo es como un mapa que dice: "Si tienes k copias de cada número y evitas ciertas combinaciones de letras, el número de formas en que puedes ordenarlas no es un caos, sino que sigue una danza matemática perfecta y predecible, ya sea como Fibonacci, Jacobsthal o sus cuadrados."

Es una demostración hermosa de que, incluso en el caos aparente de mezclar letras, las matemáticas siempre encuentran un orden elegante.

Resumen técnico

1. Problema y Contexto

El artículo aborda el problema de la evitación de patrones en el contexto de las palabras k-regulares. Una palabra k-regular sobre el conjunto $[n] = \{1, 2, \dots, n\}$ es una cadena de longitud $kn$ donde cada símbolo aparece exactamente $k$ veces.

El objetivo principal es encontrar correspondencias biyectivas entre conjuntos de estas palabras que evitan ciertos patrones (subsecuencias con un orden relativo específico) y secuencias de enteros generalizadas de Fibonacci. El trabajo se centra en dos familias de generalizaciones de Fibonacci que dependen de un segundo parámetro $k$:

1. Números Fibonacci-k ($a_k(n)$): Definidos por la recurrencia $a_k(n) = a_k(n-1) + k \cdot a_k(n-2)$.
2. Números k-Fibonacci ($b_k(n)$): Definidos por la recurrencia $b_k(n) = k \cdot b_k(n-1) + b_k(n-2)$.

Ambas secuencias utilizan los casos base $a_k(0)=a_k(1)=1$ y $b_k(0)=b_k(1)=1$. El artículo busca demostrar que el número de palabras k-regulares que evitan ciertos conjuntos de patrones coincide exactamente con estos números.

2. Metodología

Los autores emplean una metodología combinatoria directa basada en descomposición recursiva y bijecciones. A diferencia de trabajos anteriores que utilizaban funciones generadoras o descomposiciones complejas en el contexto de permutaciones de Stirling, este enfoque es más simple y constructivo:

• Análisis Estructural: Se estudian las restricciones impuestas por la evitación de patrones para determinar qué símbolos pueden preceder o seguir a otros en una palabra válida.
• Lemas de Restricción: Se prueban lemas que limitan la posición relativa de los símbolos (por ejemplo, si una palabra evita ciertos patrones, el símbolo más pequeño que puede aparecer antes de $y$ es necesariamente $y-1$).
• Construcción Recursiva: Se demuestra que cualquier palabra válida de longitud $kn$ puede construirse insertando copias del símbolo más grande ($n$) y del siguiente más grande ($n-1$) en posiciones específicas de palabras válidas de menor longitud ($n-1$ o $n-2$).
• Árboles Prefijos: Para el caso de los cuadrados de Fibonacci, se introduce una estructura de árbol (Prefix-tree $T_n$) para visualizar y contar las "anexos" (prefijos) válidos de las palabras.

3. Contribuciones Clave y Resultados Principales

El artículo presenta tres teoremas principales que establecen nuevas conexiones entre la teoría de patrones y las secuencias numéricas:

Teorema 1: Palabras Fibonacci-k

Se demuestra que el número de palabras k-regulares sobre $[n]$ que evitan los patrones $\{121, 123, 132, 213\}$ es igual al número Fibonacci-k $a_k(n)$.

• Fórmula: $a_k(n) = |\text{Av}_n^k(121, 123, 132, 213)|$.
• Significado: Esto generaliza un resultado clásico de Simion y Schmidt (1985) sobre permutaciones (donde $k=1$) y un resultado previo de Kuba y Panholzer (2012) sobre permutaciones de Stirling (donde $k=2$ y se evita 212, equivalente a 121 bajo simetría).
• Ejemplo: Para $k=2$, la secuencia es la de Jacobsthal (1, 1, 3, 5, 11...).

Teorema 2: Palabras k-Fibonacci

Se introduce un nuevo resultado para $k \ge 2$. El número de palabras k-regulares sobre $[n]$ que evitan los patrones $\{122, 213\}$ es igual al número k-Fibonacci $b_k(n)$.

• Fórmula: $b_k(n) = |\text{Av}_n^k(122, 213)|$.
• Distinción: A diferencia del Teorema 1, este resultado no se aplica a $k=1$ (donde los números de Catalan no siguen una recurrencia de dos términos simple). Para $k=2$, la secuencia es 1, 1, 3, 7, 17... (A001333).
• Importancia: Proporciona una generalización natural para palabras que no evitan el patrón 121 (no son permutaciones de Stirling), utilizando el patrón multi-patrón 122.

Teorema 3 (Teorema 5 en el texto): Secuencia de Fibonacci al Cuadrado

Se demuestra que si se "vinculariza" (hace consecutivo) el patrón 121 en el Teorema 1 para el caso $k=2$, el conteo cambia de la secuencia de Jacobsthal a los cuadrados de los números de Fibonacci.

• Definición: Se consideran palabras 2-regulares que evitan el patrón consecutivo 121 (donde los símbolos deben estar adyacentes) junto con 123, 132 y 213.
• Resultado: $|\text{Av}_n^2(121, 123, 132, 213)| = a_1(n)^2 = F_{n+1}^2$.
• Método: Se utiliza una descomposición de "anexo-base" y un árbol prefijo ($T_n$) para probar una nueva recurrencia de tres términos para la secuencia de cuadrados de Fibonacci.

4. Discusión y Significado

• Simplificación de Pruebas: El artículo ofrece una prueba combinatoria directa y simple para un resultado conocido (Teorema 1), evitando la complejidad de las funciones generadoras y las expansiones de fracciones parciales utilizadas en trabajos previos de Kuba y Panholzer.
• Unificación de Conceptos: Conecta la teoría de permutaciones de Stirling, las palabras regulares y las secuencias de Fibonacci generalizadas bajo un marco unificado de evitación de patrones.
• Nuevas Direcciones:
  • Introduce el estudio de patrones multi-patrón (como 122) en palabras regulares, mostrando que surgen secuencias de Fibonacci diferentes a las clásicas.
  • Explora la combinación de patrones clásicos y patrones vinculares (consecutivos), demostrando que esta modificación simple transforma la secuencia de Jacobsthal en los cuadrados de Fibonacci.
• Conjeturas: El artículo concluye con una conjetura (Conjetura 1) sobre el conteo de palabras r-regulares que evitan pares específicos de patrones (123 y 121, o 132 y 212), proporcionando una fórmula cerrada compleja basada en coeficientes binomiales.

Conclusión

Este trabajo es significativo porque demuestra que las palabras k-regulares son un objeto de estudio fértil para la evitación de patrones, capaz de generar y explicar diversas secuencias de enteros famosas (Fibonacci, Jacobsthal, Pell, Catalan) mediante la selección adecuada de patrones a evitar. Además, establece una base para futuras investigaciones sobre patrones no clásicos y generalizaciones paramétricas en combinatoria.