Distributions of Inversions and Descents over Integer Compositions

Technische Samenvatting: Verdelingen van Inversies en Descents over Geheeltallige Composities

Probleemstelling
Het artikel behandelt de telling van geheeltallige composities, met name gericht op de verdeling van twee fundamentele permutatiestatistieken—inversies en descents—toegepast op composities. Een $k$-compositie van een geheel getal $n$ wordt gedefinieerd als een geordende $k$-tupel van positieve gehele getallen die optellen tot $n. Hoewel eerdere literatuur (bijvoorbeeld Heubach et al., Knopfmacher et al.) genererende functies had vastgesteld voor specifieke gevallen of asymptotisch gedrag van inversietellingen in composities, heeft dit werk tot doel expliciete genererende functies af te leiden voor de algemene gevallen:

1. Het aantal $k$-composities van $n$ met een specifiek aantal inversies ($icr(n, k)$).
2. Het aantal $k$-composities van $n$ met een specifiek aantal descents ($dcr(n, k)$).
3. De corresponderende univariate gevallen waarbij $k$ onbeperkt is ($icr(n)$ en $dcr(n)$).

Methodologie
De kernbenadering rust op een bijectieve afbeelding tussen de verzameling van $k$-composities ($C_k$) en paren bestaande uit een permutatie ($\pi \in S_k$) en een geheeltallige partitie ($\lambda$). Deze bijectie, toegeschreven aan MacMahon, koppelt een compositie $\sigma$ aan een unieke permutatie $\pi$ (die de delen van $\sigma$ sorteert in zwak dalende volgorde met specifieke regels voor het oplossen van gelijke waarden) en een partitie $\lambda$ zodanig dat:
$$|\sigma| = |\lambda| + \text{maj}(\pi)$$
waarbij $|\cdot|$ de som van de delen aanduidt en $\text{maj}$ de major index aanduidt.

De auteur maakt gebruik van deze bijectie om aan te tonen dat statistieken op composities direct worden gecodeerd door corresponderende statistieken op de bijbehorende permutaties. Specifiek:

• Het inversienummer van een compositie $\sigma$ komt overeen met het inversienummer van de bijbehorende permutatie $\pi$.
• Het descentnummer van $\sigma$ heeft betrekking op het descentnummer van de inverse permutatie $\pi^{-1}$ (of equivalent, de major index van $\pi$ via de Foata-bijectie).
• De comajor index van $\sigma$ komt overeen met de inverse major index van $\pi$.

Door gebruik te maken van bekende genererende functies voor gezamenlijke statistieken over de symmetrische groep $S_k$—specifiek de verdeling van $(\text{maj}, \text{inv})$ en $(\text{inv}, \text{des})$—vertaalt het artikel deze resultaten naar genererende functies voor composities. De afleiding omvat standaard $q$-analoog-notatie, Gaussische binomiale coëfficiënten en Schur-functies.

Belangrijkste Bijdragen en Resultaten

1. Algemene Genererende Functies voor Inversies:
   Het artikel leidt een bivariate genererende functie af voor het aantal $k$-composities van $n$ met $r$ inversies. Stelling 10 stelt vast dat de verdeling van inversies over $C_k$ gerelateerd is aan de verdeling van $(\text{maj}, \text{inv})$ over $S_k$.

   • Corollarium 11 biedt de expliciete genererende functie $IC_q(p, k)$ in de vorm van een som over partities $\lambda \vdash k$ die $f^\lambda(p)f^\lambda(q)$ omvatten, waarbij $f^\lambda(q)$ de $q$-analoog is van het aantal standaard Young-tableaus van vorm $\lambda$.
   • Er wordt ook een recursierelatie voor $IC_q(p, k)$ gegeven, die de berekening van coëfficiënten mogelijk maakt zonder te sommeren over alle partities.

2. Algemene Genererende Functies voor Descents:
   Evenzo leidt het artikel de genererende functie af voor het aantal $k$-composities met een gegeven aantal descents.

   • Corollarium 12 drukt de genererende functie $DC_t(q, k)$ uit met behulp van de $q$-Eulerische polynomen $A_k(q, t)$, die de verdeling van $(\text{inv}, \text{des})$ over $S_k$ beschrijven.
   • Het resultaat wordt gegeven als een som over partities die de statistiek $g_\lambda(q)$ omvatten, die tableaus telt gewogen op basis van descentverzamelingen.

3. Gefuseerd Kader:
   Het artikel verenigt de behandeling van deze statistieken door aan te tonen dat elke statistiek op composities die via de bijectie naar $S_k$ uitdrukbaar is, geanalyseerd kan worden met behulp van de bekende gezamenlijke verdelingen van permutatiestatistieken. Dit omvat de gezamenlijke verdeling van som, major index en descentnummer.

4. Expliciete Waarden en OEIS-Verbindingen:
   De auteur berekent en somt expliciete waarden op voor $icr(n)$ en $dcr(n)$ voor $n$ tot en met 16, en levert data die overeenkomen met bestaande vermeldingen in de On-Line Encyclopedia of Integer Sequences (OEIS A189074, A238343, A238344).

Betekenis
Het artikel claimt voornamelijk betekenis door zijn vermogen om expliciete uitdrukkingen te bieden voor genererende functies die eerder alleen bekend waren voor specifieke gevallen of complexe inclusie-exclusieprincipes vereisten om af te leiden. Door een directe link te leggen tussen compositiesstatistieken en permutatiestatistieken via de MacMahon-bijectie, vereenvoudigt het werk de afleiding van deze genererende functies.

De auteur merkt op dat hoewel de computationele complexiteit van het extraheren van coëfficiënten uit de op partities gebaseerde sommen exponentieel groeit met $n$, de methode efficiënter blijft dan brute-force telling van alle $2^{n-1}$ composities. Het werk dient als een uitgebreide referentie voor de verdelingen van inversies en descents in geheeltallige composities, en breidt de notatie en resultaten van eerdere onderzoekers zoals Heubach et al. en Knopfmacher et al. uit tot algemene $n$, $k$ en $r$.