Classical Fibonacci compositions

Résumé Technique : Compositions de Fibonacci Classiques

Énoncé du Problème
L'article étudie trois types distincts de compositions d'entiers restreintes dont le dénombrement correspond à la suite de Fibonacci ($F_n$). Alors que le dénombrement général des compositions d'un entier $n$ est connu pour être $2^{n-1}$, ce travail se concentre sur des sous-ensembles définis par des contraintes spécifiques sur leurs parties :

1. Compositions Prosodiques ($C_{12}(n)$) : Compositions de $n$ où les parties sont restreintes à l'ensemble $\{1, 2\}$. Ce modèle provient de la prosodie indienne ancienne (spécifiquement les travaux de Pingala et d'érudits ultérieurs) concernant le comptage des syllabes longues et courtes dans les mètres poétiques.
2. Compositions à Parties Impaires ($C_o(n)$) : Compositions de $n$ où toutes les parties sont des entiers impairs. Ce type a été analysé par Augustus De Morgan dans l'Angleterre du XIXe siècle.
3. Compositions à Grandes Parties ($\hat{C}_1(n)$) : Compositions de $n$ où toutes les parties sont au moins égales à 2. Ce type a été considéré par Arthur Cayley en 1876.
   L'objectif de l'article est de fournir des preuves combinatoires pour le dénombrement de ces ensembles et de démontrer comment ils satisfont la relation de récurrence de Fibonacci ($F_n = F_{n-1} + F_{n-2}$) par des arguments de pavage.

Méthodologie
La méthodologie principale employée est la preuve combinatoire via des arguments de pavage. L'auteur modélise une composition de $n$ comme un pavage d'un tableau de $1 \times n$ :

• Une partie de taille $k$ correspond à une tuile de $1 \times k$.
• La séquence des parties correspond à l'arrangement des tuiles.
• Séquences de Coupe/Jonction : L'auteur utilise le concept de Percy MacMahon consistant à représenter les compositions comme des séquences binaires de choix de "Coupe" (C) et de "Jonction" (J) entre $n$ cellules.
• Bijections : Le cœur des preuves consiste à établir des bijections explicites entre l'ensemble des compositions de $n$ et l'union disjointe des compositions de $n-1$ et $n-2$. Cette décomposition structurelle reflète directement la récurrence de Fibonacci.
• Conjugaison : L'article emploie la notion de "compositions conjuguées" de MacMahon, où la séquence de coupe/jonction d'une composition est inversée (échange de C et J) pour générer une nouvelle composition. Cette opération est centrale dans le théorème final.

Contributions Clés et Résultats

1. Dénombrement des Compositions Prosodiques ($C_{12}(n)$) :

   • Résultat : $c_{12}(n) = F_{n+1}$.
   • Preuve : Une bijection est établie entre $C_{12}(n)$ et $C_{12}(n-1) \cup C_{12}(n-2)$. Une composition dans $C_{12}(n-2)$ est mappée vers $C_{12}(n)$ en ajoutant une partie de 2 (un domino), tandis qu'une composition dans $C_{12}(n-1)$ est mappée en ajoutant une partie de 1 (un carré). La distinction réside dans la dernière partie de la composition résultante.

2. Dénombrement des Compositions à Parties Impaires ($C_o(n)$) :

   • Résultat : $c_o(n) = F_n$.
   • Preuve : Une bijection mappe $C_o(n-2)$ vers $C_o(n)$ en augmentant la dernière partie $k$ à $k+2$ (préservant la parité impaire), et mappe $C_o(n-1)$ vers $C_o(n)$ en ajoutant une partie de 1. Les ensembles sont distingués par le fait que la dernière partie soit 1 ou $\ge 3$.

3. Dénombrement des Compositions à Grandes Parties ($\hat{C}_1(n)$) :

   • Résultat : $\hat{c}_1(n) = F_{n-1}$ pour $n \ge 2$.
   • Preuve : Une bijection mappe $\hat{C}_1(n-2)$ vers $\hat{C}_1(n)$ en ajoutant une partie de 2, et mappe $\hat{C}_1(n-1)$ vers $\hat{C}_1(n)$ en augmentant la dernière partie $k$ à $k+1$. La distinction est faite selon que la dernière partie est exactement 2 ou $\ge 3$.

4. Synthèse via la Conjugaison (Théorème 4) :

   • Résultat : Pour $n \ge 2$, il existe une bijection $C_{12}(n) \cong \hat{C}_1(n) \cup C_o(n)$.
   • Signification : Ce résultat fournit une réalisation combinatoire directe de l'identité $F_{n+1} = F_n + F_{n-1}$ en montrant que l'ensemble des compositions avec des parties $\{1, 2\}$ peut être partitionné (via une application spécifique impliquant la conjugaison) en l'ensemble des compositions avec des parties $\ge 2$ et l'ensemble des compositions avec des parties impaires.
   • Mécanisme : La preuve utilise la conjugaison de MacMahon. Pour une composition dans $\hat{C}_1(n)$, sa conjuguée n'a pas de termes "Jonction" adjacents (pas de parties $>2$) et commence/finit par 1 ; en retirant ces 1 de bordure et en ajoutant un 2, on obtient un élément de $C_{12}(n)$. Pour $C_o(n)$, les parties impaires sont développées en séquences de 2 et un dernier 1.

Signification et Revendications
L'article affirme fournir des preuves combinatoires rigoureuses pour des résultats de dénombrement bien connus, reliant la prosodie indienne ancienne aux mathématiques anglaises du XIXe siècle. L'auteur souligne que, bien que les résultats numériques ($c_{12}(n) = F_{n+1}$, etc.) soient connus, les preuves bijectives spécifiques utilisant le pavage et la conjugaison offrent des outils distincts pour prouver les identités de Fibonacci.

L'auteur note que différents types de compositions offrent des degrés de facilité variables pour prouver des identités spécifiques (par exemple, les sommes des nombres de Fibonacci d'indices pairs ou impairs). L'article conclut modestement, en déclarant que la bijection du Théorème 4 (reliant $C_{12}$, $\hat{C}_1$ et $C_o$) peut être une contribution nouvelle, fournissant un cadre combinatoire unifié pour la relation de récurrence $F_{n+1} = F_n + F_{n-1}$ à travers le prisme des compositions d'entiers restreintes. Le travail sert de ressource pour les preuves combinatoires d'identités de Fibonacci, faisant référence à son propre ouvrage et aux travaux de Benjamin et Quinn comme contexte pour ces méthodes.