Distributions of Inversions and Descents over Integer Compositions

Résumé technique : Distributions des inversions et des descentes sur les compositions d'entiers

Énoncé du problème
L'article traite de l'énumération des compositions d'entiers, en se concentrant spécifiquement sur la distribution de deux statistiques fondamentales des permutations — les inversions et les descentes — appliquées aux compositions. Une $k$-composition d'un entier $n$ est définie comme un $k$-uplet ordonné d'entiers positifs dont la somme est égale à $n$. Alors que la littérature antérieure (par exemple, Heubach et al., Knopfmacher et al.) avait établi des fonctions génératrices pour des cas spécifiques ou des comportements asymptotiques des nombres d'inversions dans les compositions, ce travail vise à dériver des fonctions génératrices explicites pour les cas généraux :

1. Le nombre de $k$-compositions de $n$ avec un nombre spécifique d'inversions ($icr(n, k)$).
2. Le nombre de $k$-compositions de $n$ avec un nombre spécifique de descentes ($dcr(n, k)$).
3. Les cas univariés correspondants où $k$ n'est pas restreint ($icr(n)$ et $dcr(n)$).

Méthodologie
L'approche centrale repose sur une application bijective entre l'ensemble des $k$-compositions ($C_k$) et des paires constituées d'une permutation ($\pi \in S_k$) et d'une partition d'entiers ($\lambda$). Cette bijection, attribuée à MacMahon, associe une composition $\sigma$ à une permutation unique $\pi$ (qui trie les parties de $\sigma$ par ordre décroissant faible avec des règles spécifiques de rupture d'égalité) et à une partition $\lambda$ telle que :
$$|\sigma| = |\lambda| + \text{maj}(\pi)$$
où $|\cdot|$ désigne la somme des parties et $\text{maj}$ désigne l'indice majeur.

L'auteur exploite cette bijection pour démontrer que les statistiques sur les compositions sont directement encodées par les statistiques correspondantes sur les permutations associées. Plus précisément :

• Le nombre d'inversions d'une composition $\sigma$ correspond au nombre d'inversions de la permutation associée $\pi$.
• Le nombre de descentes de $\sigma$ est lié au nombre de descentes de la permutation inverse $\pi^{-1}$ (ou de manière équivalente, à l'indice majeur de $\pi$ via la bijection de Foata).
• L'indice comajeur de $\sigma$ correspond à l'indice majeur inverse de $\pi$.

En utilisant les fonctions génératrices connues pour les statistiques conjointes sur le groupe symétrique $S_k$ — spécifiquement la distribution de $(\text{maj}, \text{inv})$ et de $(\text{inv}, \text{des})$ — l'article traduit ces résultats en fonctions génératrices pour les compositions. La dérivation fait appel à la notation standard des $q$-analogues, aux coefficients binomiaux de Gauss et aux fonctions de Schur.

Contributions et résultats clés

1. Fonctions génératrices générales pour les inversions :
   L'article dérive une fonction génératrice bivariée pour le nombre de $k$-compositions de $n$ ayant $r$ inversions. Le théorème 10 établit que la distribution des inversions sur $C_k$ est liée à la distribution de $(\text{maj}, \text{inv})$ sur $S_k$.

   • Le Corollaire 11 fournit la fonction génératrice explicite $IC_q(p, k)$ sous forme d'une somme sur les partitions $\lambda \vdash k$ impliquant $f^\lambda(p)f^\lambda(q)$, où $f^\lambda(q)$ est le $q$-analogue du nombre de tableaux de Young standards de forme $\lambda$.
   • Une relation de récurrence pour $IC_q(p, k)$ est également fournie, permettant le calcul des coefficients sans sommer sur toutes les partitions.

2. Fonctions génératrices générales pour les descentes :
   De même, l'article dérive la fonction génératrice pour le nombre de $k$-compositions avec un nombre donné de descentes.

   • Le Corollaire 12 exprime la fonction génératrice $DC_t(q, k)$ à l'aide des polynômes $q$-eulériens $A_k(q, t)$, qui décrivent la distribution de $(\text{inv}, \text{des})$ sur $S_k$.
   • Le résultat est donné comme une somme sur les partitions impliquant la statistique $g_\lambda(q)$, qui compte les tableaux pondérés par les ensembles de descentes.

3. Cadre unifié :
   L'article unifie le traitement de ces statistiques en montrant que toute statistique sur les compositions, exprimable via la bijection vers $S_k$, peut être analysée à l'aide des distributions conjointes connues des statistiques de permutation. Cela inclut la distribution conjointe de la somme, de l'indice majeur et du nombre de descentes.

4. Valeurs explicites et liens avec l'OEIS :
   L'auteur calcule et liste les valeurs explicites pour $icr(n)$ et $dcr(n)$ pour $n$ allant jusqu'à 16, fournissant des données qui correspondent aux entrées existantes de l'On-Line Encyclopedia of Integer Sequences (OEIS A189074, A238343, A238344).

Signification
L'article revendique une importance principalement dans sa capacité à fournir des expressions explicites pour des fonctions génératrices qui n'étaient auparavant connues que pour des cas spécifiques ou qui nécessitaient des principes complexes d'inclusion-exclusion pour être dérivées. En établissant un lien direct entre les statistiques des compositions et les statistiques des permutations via la bijection de MacMahon, ce travail simplifie la dérivation de ces fonctions génératrices.

L'auteur note que, bien que la complexité computationnelle de l'extraction des coefficients à partir des sommes basées sur les partitions croisse de manière exponentielle avec $n$, la méthode reste plus efficace que l'énumération brute de toutes les $2^{n-1}$ compositions. Ce travail sert de référence complète pour les distributions des inversions et des descentes dans les compositions d'entiers, étendant la notation et les résultats de chercheurs précédents tels que Heubach et al. et Knopfmacher et al. aux cas généraux de $n$, $k$ et $r$.