Classical Fibonacci compositions

Resumen Técnico: Composiciones de Fibonacci Clásicas

Planteamiento del Problema
El artículo investiga tres tipos distintos de composiciones de enteros restringidas cuyas enumeraciones cuentan con la secuencia de Fibonacci ($F_n$). Mientras que el recuento general de las composiciones de un entero $n$ es conocido como $2^{n-1}$, este trabajo se centra en subconjuntos definidos por restricciones específicas en sus partes:

1. Composiciones Prosódicas ($C_{12}(n)$): Composiciones de $n$ donde las partes están restringidas al conjunto $\{1, 2\}$. Este modelo se origina en la antigua prosodia india (específicamente en las obras de Pingala y estudiosos posteriores) con respecto al conteo de sílabas largas y cortas en los metros poéticos.
2. Composiciones de Partes Impares ($C_o(n)$): Composiciones de $n$ donde todas las partes son enteros impares. Este tipo fue analizado por Augustus De Morgan en la Inglaterra del siglo XIX.
3. Composiciones de Partes Grandes ($\hat{C}_1(n)$): Composiciones de $n$ donde todas las partes son al menos 2. Este tipo fue considerado por Arthur Cayley en 1876.

El objetivo del artículo es proporcionar pruebas combinatorias para la enumeración de estos conjuntos y demostrar cómo satisfacen la relación de recurrencia de Fibonacci ($F_n = F_{n-1} + F_{n-2}$) mediante argumentos de teselado (tiling).

Metodología
La metodología principal empleada es la prueba combinatoria mediante argumentos de teselado. El autor modela una composición de $n$ como un teselado de un tablero de $1 \times n$:

• Una parte de tamaño $k$ corresponde a una tesela de $1 \times k$.
• La secuencia de partes corresponde al arreglo de las teselas.
• Secuencias de Corte/Unión (Cut/Join): El autor utiliza el concepto de Percy MacMahon de representar composiciones como secuencias binarias de elecciones de "Corte" (C) y "Unión" (J) entre $n$ celdas.
• Bijecciones: El núcleo de las pruebas consiste en establecer bijecciones explícitas entre el conjunto de composiciones de $n$ y la unión disjunta de las composiciones de $n-1$ y $n-2$. Esta descomposición estructural refleja directamente la recurrencia de Fibonacci.
• Conjugación: El artículo emplea la noción de "composiciones conjugadas" de MacMahon, donde la secuencia de corte/unión de una composición se invierte (intercambiando C y J) para generar una nueva composición. Esta operación es central para el teorema final.

Contribuciones Clave y Resultados

1. Enumeración de Composiciones Prosódicas ($C_{12}(n)$):

   • Resultado: $c_{12}(n) = F_{n+1}$.
   • Prueba: Se establece una biyección entre $C_{12}(n)$ y $C_{12}(n-1) \cup C_{12}(n-2)$. Una composición en $C_{12}(n-2)$ se mapea a $C_{12}(n)$ añadiendo una parte de 2 (un dominó), mientras que una composición en $C_{12}(n-1)$ se mapea añadiendo una parte de 1 (un cuadrado). La distinción radica en la última parte de la composición resultante.

2. Enumeración de Composiciones de Partes Impares ($C_o(n)$):

   • Resultado: $c_o(n) = F_n$.
   • Prueba: Una biyección mapea $C_o(n-2)$ a $C_o(n)$ aumentando la última parte $k$ a $k+2$ (preservando la imparidad), y mapea $C_o(n-1)$ a $C_o(n)$ añadiendo una parte de 1. Los conjuntos se distinguen por si la última parte es 1 o $\ge 3$.

3. Enumeración de Composiciones de Partes Grandes ($\hat{C}_1(n)$):

   • Resultado: $\hat{c}_1(n) = F_{n-1}$ para $n \ge 2$.
   • Prueba: Una biyección mapea $\hat{C}_1(n-2)$ a $\hat{C}_1(n)$ añadiendo una parte de 2, y mapea $\hat{C}_1(n-1)$ a $\hat{C}_1(n)$ aumentando la última parte $k$ a $k+1$. La distinción se hace basada en si la última parte es exactamente 2 o $\ge 3$.

4. Síntesis mediante Conjugación (Teorema 4):

   • Resultado: Para $n \ge 2$, existe una biyección $C_{12}(n) \cong \hat{C}_1(n) \cup C_o(n)$.
   • Significado: Este resultado proporciona una realización combinatoria directa de la identidad $F_{n+1} = F_n + F_{n-1}$ al mostrar que el conjunto de composiciones con partes $\{1, 2\}$ puede particionarse (mediante un mapeo específico que involucra la conjugación) en los conjuntos de composiciones con partes $\ge 2$ y composiciones con partes impares.
   • Mecanismo: La prueba utiliza la conjugación de MacMahon. Para una composición en $\hat{C}_1(n)$, su conjugada no tiene términos "Unión" adyacentes (sin partes $>2$) y comienza/termina con 1; eliminar estos 1s de los bordes y añadir un 2 produce un elemento en $C_{12}(n)$. Para $C_o(n)$, las partes impares se expanden en secuencias de 2s y un 1 final.

Significancia y Reivindicaciones
El artículo afirma proporcionar pruebas combinatorias rigurosas para resultados de enumeración bien conocidos, conectando la antigua prosodia india con las matemáticas inglesas del siglo XIX. El autor enfatiza que, si bien los resultados numéricos ($c_{12}(n) = F_{n+1}$, etc.) eran conocidos, las pruebas biyectivas específicas utilizando teselado y conjugación ofrecen herramientas distintas para probar identidades de Fibonacci.

El autor señala que diferentes tipos de composiciones ofrecen distintos grados de facilidad para probar identidades específicas (por ejemplo, sumas de números de Fibonacci de índice par o impar). El trabajo concluye modestamente, afirmando que la biyección en el Teorema 4 (que vincula $C_{12}$, $\hat{C}_1$ y $C_o$) puede ser una contribución novedosa, proporcionando un marco combinatorio unificado para la relación de recurrencia $F_{n+1} = F_n + F_{n-1}$ a través de la lente de las composiciones de enteros restringidas. El trabajo sirve como recurso para las pruebas combinatorias de identidades de Fibonacci, haciendo referencia al propio libro del autor y al trabajo de Benjamin y Quinn como contexto para estos métodos.