Arndt and Carlitz Compositions

Résumé technique : Compositions d'Arndt et de Carlitz

Énoncé du problème
L'article traite de l'énumération des compositions d'entiers — séquences ordonnées d'entiers positifs dont la somme est $n$ — sous des restrictions locales spécifiques. Il cherche à unifier et généraliser deux lignes de recherche distinctes :

1. Compositions de Carlitz : Introduites par Carlitz, elles exigent que les parties adjacentes soient inégales ($c_i \neq c_{i+1}$).
2. Compositions d'Arndt : Initiées par Arndt, elles imposent des restrictions sur des paires spécifiques de parties, typiquement $(c_{2i-1}, c_{2i})$, sans restreindre la relation entre $c_{2i}$ et $c_{2i+1}$.

Les auteurs définissent une nouvelle classe de compositions de Carlitz–Arndt ($CA(n)$) qui satisfaisent la structure d'appariement d'Arndt mais imposent la condition de Carlitz ($c_{2i-1} \neq c_{2i}$) sur chaque paire. L'article généralise ensuite cela en bornant la différence absolue entre les parties appariées par le bas ($|c_{2i-1} - c_{2i}| \geq k$) et par le haut ($|c_{2i-1} - c_{2i}| \leq k$).

Méthodologie
Les auteurs emploient une double approche combinant des preuves combinatoires (bijections explicites) et des fonctions génératrices.

• Preuves combinatoires : Le cœur de l'article consiste à construire des bijections entre les compositions restreintes et d'autres ensembles connus ou nouvellement définis. Pour le cas de la borne inférieure, ils établissent une correspondance entre les compositions et un sous-ensemble de « compositions de Pell restreintes » ($P_{\geq k}(n)$) impliquant les parties $\{1, 1', 2\}$. Pour le cas de la borne supérieure, ils établissent une correspondance avec les compositions $Q_{\leq k}(n)$ impliquant les parties $\{1, 1', 2, 4, 6, \dots\}$. Ces bijections permettent aux auteurs de dériver des relations de récurrence en analysant la structure des ensembles correspondants.
• Fonctions génératrices : Les auteurs dérivent des fonctions génératrices rationnelles pour le nombre de compositions dans chaque classe. Ces fonctions sont construites en traitant les paires de parties comme des blocs et en sommant sur les valeurs possibles, puis en combinant les cas de longueurs paires et impaires.

Contributions clés et résultats

1. Compositions de Carlitz–Arndt ($CA(n)$) :

   • Les auteurs établissent que le nombre de ces compositions, $ca(n)$, satisfait la récurrence $ca(n) = ca(n-1) + ca(n-2) + ca(n-3)$ avec les valeurs initiales $1, 1, 3$.
   • Cette séquence correspond aux nombres « tribonacci » (OEIS A000213).
   • Une bijection est prouvée entre $CA(n)$ et les compositions sans parties adjacentes égales à 1 ($C^c_{1,1}(n)$).

2. Compositions à borne inférieure généralisée ($CA_{\geq k}(n)$) :

   • Pour un $k$ fixé, la condition $|c_{2i-1} - c_{2i}| \geq k$ est analysée.
   • Les auteurs prouvent une relation de récurrence : $ca_{\geq k}(n) = ca_{\geq k}(n-1) + ca_{\geq k}(n-2) - ca_{\geq k}(n-3) + 2ca_{\geq k}(n-k-2)$.
   • Une bijection est établie entre $CA_{\geq k}(n)$ et les compositions de Pell restreintes $P_{\geq k}(n)$, où les suites de 1 ou de $1'$ ont une longueur d'au moins $k$.
   • La fonction génératrice est dérivée comme étant $\frac{1-x^2}{1-x-x^2+x^3-2x^{k+2}}$.

3. Compositions à borne supérieure généralisée ($CA_{\leq k}(n)$) :

   • La condition $|c_{2i-1} - c_{2i}| \leq k$ est analysée.
   • Les auteurs dérivent une récurrence : $ca_{\leq k}(n) = ca_{\leq k}(n-1) + 2ca_{\leq k}(n-2) - 2ca_{\leq k}(n-k-3)$.
   • Une bijection est établie entre $CA_{\leq k}(n)$ et les compositions $Q_{\leq k}(n)$ avec les parties $\{1, 1', 2, 4, 6, \dots\}$ où les suites de 1 ou de $1'$ ont une longueur d'au plus $k$.
   • La fonction génératrice est dérivée comme étant $\frac{1-x^2}{1-x-2x^2+2x^{k+3}}$.

Signification et revendications
L'article affirme avoir réussi à combiner et généraliser les notions de compositions de Carlitz et d'Arnddt. En établissant ces connexions, les auteurs fournissent :

• Résultats d'énumération : Des relations de récurrence explicites et des fonctions génératrices pour ces classes généralisées.
• Perspective combinatoire : Les bijections avec les compositions de type Pell et les compositions à longueur de suite restreinte offrent une compréhension structurelle de la raison pour laquelle ces récurrences spécifiques apparaissent.
• Motivation contextuelle : Le travail est motivé par son lien avec les compositions sans écart (étudiées par Hitczenko et Knopfmacher) et les partitions d'entiers de Rogers–Ramanujan. Les auteurs notent que leur généralisation de la borne inférieure ($CA_{\geq k}$) est liée aux parties « super-distinctes » des partitions de Rogers–Ramanujan (parties différant d'au moins 2) et des partitions de Schur (parties différant d'au moins 3).

Les auteurs déclarent explicitement que leurs méthodes sont principalement combinatoires, bien qu'ils utilisent les fonctions génératrices pour vérifier et fournir des preuves alternatives pour les relations de récurrence. Ils reconnaissent que Prodinger (2023) a considéré une combinaison plus complexe de ces conditions, ce qui a incité les auteurs à utiliser la notation $CA(n)$ pour distinguer leur formulation spécifique. L'article ne propose pas d'applications expérimentales ou d'implications futures au-delà de l'énumération mathématique et de l'analyse structurelle présentées.