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

Cet article établit une preuve simple reliant deux types de récurrences de Fibonacci $k$-aires au dénombrement de mots $k$-régulaires évitant certains motifs, complète ce résultat par un nouveau théorème pour une autre classe de motifs, et émet une conjecture sur les nombres de Fibonacci au carré dans le contexte des motifs vinculaires.

L'essentiel

Imaginez que vous êtes un architecte chargé de construire des tours avec des blocs de couleurs. Dans ce papier de recherche, les auteurs (Emily, Elizabeth, Cody et Aaron) ne construisent pas des gratte-ciels ordinaires, mais des tours très spécifiques basées sur des règles mathématiques appelées séquences de Fibonacci.

Voici l'explication de leur travail, traduite en langage simple et illustrée par des métaphores.

1. Le Concept de Base : Les Tours "k-Régulières"

D'habitude, quand on parle de Fibonacci, on pense à une suite de nombres (1, 1, 2, 3, 5, 8...) où chaque nombre est la somme des deux précédents.

Dans ce papier, les auteurs imaginent une version "surdimensionnée" de cette suite.

• L'idée : Au lieu d'avoir un seul bloc de chaque couleur (1, 2, 3...), vous avez k blocs de chaque couleur.
• La règle : Si vous avez 3 couleurs (1, 2, 3) et que k=2, votre tour doit contenir exactement deux "1", deux "2" et deux "3". C'est ce qu'ils appellent un mot "k-régulier".

Leur but ? Compter combien de façons différentes on peut empiler ces blocs sans violer certaines règles de "défauts" (ce qu'ils appellent l'évitement de motifs).

2. Les Deux Règles du Jeu (Les Deux Théorèmes)

Les auteurs ont découvert deux façons principales de construire ces tours qui correspondent à deux nouvelles suites de nombres.

A. La Tour "Fibonacci-k" (Le Théorème 1)

Imaginez que vous avez une règle stricte : "Ne jamais mettre un petit bloc, puis un grand, puis un petit à nouveau" (comme 1-3-1). C'est le motif interdit "121". De plus, vous ne pouvez pas faire certaines autres combinaisons de hauteurs.

• La découverte : Si vous respectez ces règles, le nombre de tours possibles suit une suite mathématique appelée Fibonacci-k.
• L'analogie : C'est comme si vous aviez une recette de cuisine. Si vous suivez la recette (évitez les mauvais motifs), le nombre de plats délicieux que vous pouvez créer suit une formule précise.
• Le lien avec l'histoire : Quand k=1 (un seul bloc de chaque couleur), on retrouve la célèbre suite de Fibonacci classique. Quand k=2, on obtient une suite connue sous le nom de Jacobsthal. Les auteurs ont prouvé que cette règle fonctionne pour n'importe quel k (3, 4, 100...).

B. La Tour "k-Fibonacci" (Le Théorème 2)

Ici, les règles changent légèrement. Cette fois, l'interdiction principale est de ne pas avoir "un petit, puis deux grands identiques" (comme 1-2-2).

• La découverte : Si vous évitez ce motif spécifique, le nombre de tours possibles suit une autre suite, appelée k-Fibonacci.
• La différence : C'est comme changer la règle de l'architecte. Au lieu d'interdire le "petit-grand-petit", on interdit le "petit-grand-grand". Le résultat est une suite de nombres différente, mais tout aussi régulière.

3. Le Grand Final : Les Carrés de Fibonacci

La partie la plus fascinante du papier (Théorème 5) concerne une règle encore plus stricte.

• La situation : Reprenons la première règle (éviter 1-3-1), mais ajoutons une contrainte de "colle". Les blocs doivent être collés ensemble. Si vous avez un motif 1-2-1, les deux "1" doivent être séparés par le "2" sans aucun autre bloc entre eux. C'est ce qu'on appelle un motif "vinculaire" (comme des blocs magnétiques qui s'attirent).
• Le résultat magique : Quand on applique cette règle de "collage" aux tours à deux couleurs (k=2), le nombre de tours possibles ne suit plus la suite Jacobsthal, mais devient le carré des nombres de Fibonacci (1, 1, 4, 9, 25, 64...).
• L'image mentale : C'est comme si, en serrant un peu plus les vis de votre tour, vous aviez découvert que le nombre de structures stables possibles était exactement le nombre de Fibonacci multiplié par lui-même. C'est une surprise mathématique élégante.

En Résumé

Ce papier est une exploration de l'ordre dans le chaos. Les auteurs ont pris des règles de construction complexes (empiler des blocs de couleurs multiples) et ont découvert que :

1. En évitant certains motifs, on obtient des suites de nombres prévisibles et élégantes (les suites Fibonacci-k et k-Fibonacci).
2. En ajoutant une contrainte de "colle" (motifs consécutifs), on transforme une suite connue en une autre suite tout aussi célèbre (les carrés de Fibonacci).

C'est un peu comme si l'on découvrait que, dans un immense labyrinthe de blocs de Lego, il existe des chemins secrets qui mènent toujours à des nombres magiques, quelle que soit la taille du labyrinthe. Les auteurs ont simplement trouvé la carte pour ces chemins.

Résumé technique

Voici un résumé technique détaillé de l'article « Pattern Avoidance for Fibonacci Sequences using k-Regular Words » (Évitement de motifs pour les suites de Fibonacci utilisant des mots k-réguliers) par Downing, Hartung, Lucido et Williams.

1. Problématique et Contexte

L'article s'inscrit dans le domaine de la combinatoire des mots et de la théorie des motifs de permutation (pattern avoidance). L'objectif principal est d'établir des correspondances biunivoques entre des familles de suites d'entiers généralisant la suite de Fibonacci et des ensembles de mots k-réguliers évitant certains motifs.

• Objets d'étude : Les mots k-réguliers sur l'ensemble $[n] = \{1, 2, \dots, n\}$, notés $S_n^k$. Un tel mot contient exactement $k$ occurrences de chaque symbole de $[n]$.
• Motifs : Les auteurs étudient l'évitement de motifs classiques (permutations de longueur 3 comme 123, 132, 213, etc.) et de motifs multi-symboles (comme 121, 122).
• Suites cibles :
  1. Les nombres Fibonacci-k : $a_k(n) = a_k(n-1) + k \cdot a_k(n-2)$ avec $a_k(0)=a_k(1)=1$.
  2. Les nombres k-Fibonacci : $b_k(n) = k \cdot b_k(n-1) + b_k(n-2)$ avec $b_k(0)=b_k(1)=1$.
  3. Les nombres Fibonacci-carrés : $c(n) = a_1(n)^2$.

L'article vise à fournir des preuves combinatoires directes et simples pour ces énumérations, complétant ou simplifiant des résultats antérieurs (notamment ceux de Kuba et Panholzer) et découvrant de nouvelles classes d'évitement.

2. Méthodologie

La méthodologie repose sur une analyse structurelle récursive des mots k-réguliers évitant les motifs spécifiés. Les auteurs utilisent les techniques suivantes :

• Décomposition par le dernier symbole (ou le plus grand) : Pour un mot évitant certains motifs, ils analysent la position des occurrences du plus grand symbole $n$.
• Lemmes de contrainte : Ils établissent des lemmes démontrant que, sous certaines conditions d'évitement, le plus petit symbole pouvant précéder un symbole $y$ est nécessairement $y-1$. Cela restreint drastiquement la structure des mots valides.
• Bijections et récurrence : En identifiant les formes canoniques des préfixes valides, ils démontrent que l'ensemble des mots valides se partitionne en sous-ensembles isomorphes à des ensembles de mots de taille inférieure ($n-1$ ou $n-2$). Cela permet de dériver les relations de récurrence caractéristiques des suites de Fibonacci.
• Arbres de préfixes (Prefix-trees) : Pour le cas des nombres Fibonacci-carrés, ils introduisent une structure arborescente complexe ($T_n$) pour modéliser les "annexes" (préfixes) possibles des mots, reliant la structure du mot à des chemins dans un arbre.
• Motifs vinculaires : Pour le dernier résultat, ils utilisent la notion de motifs vinculaires (consecutifs), où les symboles du motif doivent être adjacents dans le mot, modifiant ainsi la contrainte d'évitement du motif 121.

3. Contributions et Résultats Clés

L'article présente trois théorèmes principaux :

A. Théorème 1 : Les mots Fibonacci-k

Les auteurs prouvent que le nombre de mots k-réguliers sur $[n]$ évitant les motifs $\{121, 123, 132, 213\}$ est exactement égal au nombre Fibonacci-k $a_k(n)$.

• Formule : $|Av_n^k(121, 123, 132, 213)| = a_k(n)$.
• Cas particuliers :
  • Pour $k=1$, on retrouve le résultat classique de Simion et Schmidt sur les permutations évitant $\{123, 132, 213\}$ (suite de Fibonacci standard).
  • Pour $k=2$, on obtient la suite de Jacobsthal (A001045).
• Apport : Bien que ce résultat ait été prouvé précédemment par Kuba et Panholzer dans un contexte plus large (permutations de Stirling), les auteurs fournissent une preuve combinatoire directe et simplifiée basée sur une décomposition récursive simple.

B. Théorème 2 : Les mots k-Fibonacci

Ils établissent un nouveau résultat pour les mots évitant $\{122, 213\}$. Le nombre de tels mots k-réguliers est égal au nombre k-Fibonacci $b_k(n)$.

• Formule : $|Av_n^k(122, 213)| = b_k(n)$ pour $k \ge 2$.
• Distinction : Ce résultat est valide pour $k \ge 2$. Pour $k=1$, les mots évitant $\{122, 213\}$ correspondent aux permutations évitant 213, qui sont comptées par les nombres de Catalan, et non par la suite k-Fibonacci.
• Apport : C'est une nouvelle classe d'évitement qui généralise les suites de type Pell et autres suites linéaires récurrentes.

C. Théorème 5 : Les mots Fibonacci-carrés

Les auteurs montrent que si l'on impose que le motif 121 soit vinculaire (c'est-à-dire que les occurrences de 1 et 2 doivent être consécutives, noté souvent $1\text{-}2\text{-}1$ou motif consécutif), alors le nombre de mots 2-réguliers évitant${121, 123, 132, 213}$ (avec 121 traité comme consécutif) est égal au carré des nombres de Fibonacci standards.

• Formule : $|Av_n^2(121, 123, 132, 213)| = a_1(n)^2 = c(n)$.
• Apport : Cela transforme la suite de Jacobsthal (résultat pour $k=2$ sans contrainte de consécutivité) en une suite de nombres Fibonacci-carrés (A007598) grâce à une contrainte de contiguïté. La preuve utilise une décomposition en "annexes" et "bases" via un arbre de préfixes spécifique.

4. Signification et Impact

• Unification et Simplification : L'article offre des preuves élémentaires pour des résultats complexes, rendant la structure sous-jacente des mots k-réguliers plus accessible. Il clarifie la relation entre les suites de Fibonacci généralisées et l'évitement de motifs.
• Extension des classes d'évitement : Il élargit le champ de l'évitement de motifs au-delà des permutations classiques ($k=1$) et des mots de Stirling, en introduisant de nouvelles familles de mots réguliers avec des propriétés d'énumération riches.
• Nouvelles connexions : La découverte que l'ajout d'une contrainte de motif vinculaire (121 consécutif) fait passer d'une suite de Jacobsthal à une suite de Fibonacci-carrés est un résultat surprenant et élégant, suggérant de nouvelles pistes pour l'étude des motifs non classiques (barred, dotted, mesh, etc.) dans les mots réguliers.
• Conjectures : L'article propose une conjecture (Conjecture 1) pour l'évitement de paires de motifs $(123, 121)$ et $(132, 212)$ dans les mots r-réguliers, fournissant une formule combinatoire complexe et des données pour l'OEIS, ouvrant la voie à de futures recherches.

En résumé, cet article démontre la puissance des mots k-réguliers comme cadre unificateur pour l'étude des suites récurrentes linéaires d'ordre 2 et ouvre de nouvelles perspectives sur l'interaction entre la structure des mots et les contraintes de motifs classiques et non classiques.