Classical Fibonacci compositions

Resumo Técnico: Composições de Fibonacci Clássicas

Enunciado do Problema
O artigo investiga três tipos distintos de composições de inteiros restritas cujas contagens de enumeração correspondem à sequência de Fibonacci ($F_n$). Embora a contagem geral de composições de um inteiro $n$ seja conhecida como $2^{n-1}$, este trabalho foca em subconjuntos definidos por restrições específicas em suas partes:

1. Composições Prosódicas ($C_{12}(n)$): Composições de $n$ onde as partes são restritas ao conjunto $\{1, 2\}$. Este modelo origina-se da antiga prosódia indiana (especificamente as obras de Pingala e estudiosos posteriores) em relação à contagem de sílabas longas e curtas em métrica poética.
2. Composições de Partes Ímpares ($C_o(n)$): Composições de $n$ onde todas as partes são inteiros ímpares. Este tipo foi analisado por Augustus De Morgan na Inglaterra do século XIX.
3. Composições de Partes Grandes ($\hat{C}_1(n)$): Composições de $n$ onde todas as partes são pelo menos 2. Este tipo foi considerado por Arthur Cayley em 1876.
   O artigo visa fornecer provas combinatórias para a enumeração desses conjuntos e demonstrar como eles satisfazem a relação de recorrência de Fibonacci ($F_n = F_{n-1} + F_{n-2}$) através de argumentos de ladrilhamento (tiling).

Metodologia
A principal metodologia empregada é a prova combinatória via argumentos de ladrilhamento. O autor modela uma composição de $n$ como um ladrilhamento de um tabuleiro $1 \times n$:

• Uma parte de tamanho $k$ corresponde a um ladrilho de $1 \times k$.
• A sequência de partes corresponde ao arranjo dos ladrilhos.
• Sequências de Corte/Junção (Cut/Join): O autor utiliza o conceito de Percy MacMahon de representar composições como sequências binárias de escolhas de "Corte" (C) e "Junção" (J) entre $n$ células.
• Bijeções: O núcleo das provas envolve estabelecer bijeções explícitas entre o conjunto de composições de $n$ e a união disjunta de composições de $n-1$ e $n-2$. Essa decomposição estrutural reflete diretamente a recorrência de Fibonacci.
• Conjugação: O artigo emprega a noção de "composições conjugadas" de MacMahon, onde a sequência de corte/junção de uma composição é invertida (trocando C por J) para gerar uma nova composição. Esta operação é central para o teorema final.

Principais Contribuições e Resultados

1. Enumeração de Composições Prosódicas ($C_{12}(n)$):

   • Resultado: $c_{12}(n) = F_{n+1}$.
   • Prova: Uma bijeção é estabelecida entre $C_{12}(n)$ e $C_{12}(n-1) \cup C_{12}(n-2)$. Uma composição em $C_{12}(n-2)$ é mapeada para $C_{12}(n)$ anexando uma parte de 2 (um dominó), enquanto uma composição em $C_{12}(n-1)$ é mapeada anexando uma parte de 1 (um quadrado). A distinção reside na parte final da composição resultante.

2. Enumeração de Composições de Partes Ímpares ($C_o(n)$):

   • Resultado: $c_o(n) = F_n$.
   • Prova: Uma bijeção mapeia $C_o(n-2)$ para $C_o(n)$ aumentando a parte final $k$ para $k+2$ (preservando a imparidade), e mapeia $C_o(n-1)$ para $C_o(n)$ anexando uma parte de 1. Os conjuntos são distinguidos se a parte final é 1 ou $\ge 3$.

3. Enumeração de Composições de Partes Grandes ($\hat{C}_1(n)$):

   • Resultado: $\hat{c}_1(n) = F_{n-1}$ para $n \ge 2$.
   • Prova: Uma bijeção mapeia $\hat{C}_1(n-2)$ para $\hat{C}_1(n)$ anexando uma parte de 2, e mapeia $\hat{C}_1(n-1)$ para $\hat{C}_1(n)$ aumentando a parte final $k$ para $k+1$. A distinção é feita com base se a parte final é exatamente 2 ou $\ge 3$.

4. Síntese via Conjugação (Teorema 4):

   • Resultado: Para $n \ge 2$, existe uma bijeção $C_{12}(n) \cong \hat{C}_1(n) \cup C_o(n)$.
   • Significância: Este resultado fornece uma realização combinatória direta da identidade $F_{n+1} = F_n + F_{n-1}$ ao mostrar que o conjunto de composições com partes $\{1, 2\}$ pode ser particionado (via um mapeamento específico envolvendo conjugação) nos conjuntos de composições com partes $\ge 2$ e composições com partes ímpares.
   • Mecanismo: A prova utiliza a conjugação de MacMahon. Para uma composição em $\hat{C}_1(n)$, sua conjugada não possui termos "Junção" adjacentes (nenhuma parte $>2$) e começa/termina com 1; removendo esses 1s de fronteira e anexando um 2, obtém-se um elemento em $C_{12}(n)$. Para $C_o(n)$, as partes ímpares são expandidas em sequências de 2s e um 1 final.

Significância e Alegações
O artigo afirma fornecer provas combinatórias rigorosas para resultados de enumeração bem conhecidos, conectando a antiga prosódia indiana com a matemática inglesa do século XIX. O autor enfatiza que, embora os resultados numéricos ($c_{12}(n) = F_{n+1}$, etc.) fossem conhecidos, as provas bijectivas específicas usando ladrilhamento e conjugação oferecem ferramentas distintas para provar identidades de Fibonacci.

O autor observa que diferentes tipos de composição oferecem graus variados de facilidade para provar identidades específicas (ex: somas de números de Fibonacci de índices pares ou ímpares). O artigo conclui modestamente, afirmando que a bijeção no Teorema 4 (ligando $C_{12}$, $\hat{C}_1$ e $C_o$) pode ser uma contribuição inédita, fornecendo um arcabouço combinatório unificado para a relação de recorrência $F_{n+1} = F_n + F_{n-1}$ através da ótica das composições de inteiros restritas. O trabalho serve como um recurso para provas combinatórias de identidades de Fibonacci, referenciando o próprio livro do autor e o trabalho de Benjamin e Quinn como contexto para esses métodos.