Distributions of Inversions and Descents over Integer Compositions

Technische Zusammenfassung: Verteilungen von Inversionen und Absteigern über ganzzahlige Kompositionen

Problemstellung
Der Artikel behandelt die Enumeration ganzzahliger Kompositionen mit einem spezifischen Fokus auf die Verteilung zweier fundamentaler Permutationsstatistiken – Inversionen und Absteiger (Descents) –, die auf Kompositionen angewendet werden. Eine $k$-Komposition einer ganzen Zahl $n$ ist definiert als ein geordnetes $k$-Tupel positiver ganzer Zahlen, deren Summe $n$ ergibt. Während frühere Literatur (z. B. Heubach et al., Knopfmacher et al.) erzeugende Funktionen für spezifische Fälle oder asymptotisches Verhalten von Inversionszahlen in Kompositionen etabliert hatte, zielt diese Arbeit darauf ab, explizite erzeugende Funktionen für die allgemeinen Fälle herzuleiten:

1. Die Anzahl der $k$-Kompositionen von $n$ mit einer spezifischen Anzahl von Inversionen ($icr(n, k)$).
2. Die Anzahl der $k$-Kompositionen von $n$ mit einer spezifischen Anzahl von Absteigern ($dcr(n, k)$).
3. Die entsprechenden univariaten Fälle, bei denen $k$ uneingeschränkt ist ($icr(n)$ und $dcr(n)$).

Methodik
Der Kernansatz stützt sich auf eine bijektive Abbildung zwischen der Menge der $k$-Kompositionen ($C_k$) und Paaren, die aus einer Permutation ($\pi \in S_k$) und einer ganzzahligen Partition ($\lambda$) bestehen. Diese Bijektion, die MacMahon zugeschrieben wird, ordnet einer Komposition $\sigma$ eine eindeutige Permutation $\pi$ zu (die die Teile von $\sigma$ in schwach fallender Reihenfolge mit spezifischen Regeln zur Auflösung von Gleichheiten sortiert) sowie eine Partition $\lambda$, sodass gilt:
$$|\sigma| = |\lambda| + \text{maj}(\pi)$$
wobei $|\cdot|$ die Summe der Teile bezeichnet und $\text{maj}$ den Major-Index bezeichnet.

Der Autor nutzt diese Bijektion, um zu zeigen, dass Statistiken auf Kompositionen direkt durch entsprechende Statistiken auf den zugehörigen Permutationen kodiert sind. Insbesondere:

• Die Inversionszahl einer Komposition $\sigma$ entspricht der Inversionszahl der zugehörigen Permutation $\pi$.
• Die Absteigerzahl von $\sigma$ steht in Beziehung zur Absteigerzahl der inversen Permutation $\pi^{-1}$ (oder äquivalent zum Major-Index von $\pi$ über die Foata-Bijektion).
• Der Komajor-Index von $\sigma$ entspricht dem inversen Major-Index von $\pi$.

Durch die Nutzung bekannter erzeugender Funktionen für gemeinsame Statistiken über der symmetrischen Gruppe $S_k$ – speziell die Verteilung von $(\text{maj}, \text{inv})$ und $(\text{inv}, \text{des})$ – übersetzt der Artikel diese Ergebnisse in erzeugende Funktionen für Kompositionen. Die Herleitung umfasst die Standard-$q$-Analog-Notation, gaußsche Binomialkoeffizienten und Schur-Funktionen.

Hauptbeiträge und Ergebnisse

1. Allgemeine erzeugende Funktionen für Inversionen:
   Der Artikel leitet eine bivariante erzeugende Funktion für die Anzahl der $k$-Kompositionen von $n$ mit $r$ Inversionen her. Satz 10 stellt fest, dass die Verteilung der Inversionen über $C_k$ mit der Verteilung von $(\text{maj}, \text{inv})$ über $S_k$ verknüpft ist.

   • Korollar 11 liefert die explizite erzeugende Funktion $IC_q(p, k)$ als Summe über Partitionen $\lambda \vdash k$, die $f^\lambda(p)f^\lambda(q)$ beinhaltet, wobei $f^\lambda(q)$ das $q$-Analog der Anzahl der Standard-Young-Tableaus der Form $\lambda$ ist.
   • Eine Rekursionsbeziehung für $IC_q(p, k)$ wird ebenfalls bereitgestellt, die die Berechnung der Koeffizienten ohne Summation über alle Partitionen ermöglicht.

2. Allgemeine erzeugende Funktionen für Absteiger:
   Ebenso leitet der Artikel die erzeugende Funktion für die Anzahl der $k$-Kompositionen mit einer gegebenen Anzahl von Absteigern her.

   • Korollar 12 drückt die erzeugende Funktion $DC_t(q, k)$ unter Verwendung der $q$-Euler-Polynome $A_k(q, t)$ aus, welche die Verteilung von $(\text{inv}, \text{des})$ über $S_k$ beschreiben.
   • Das Ergebnis wird als Summe über Partitionen angegeben, die die Statistik $g_\lambda(q)$ beinhaltet, welche Tableaus gewichtet nach Absteigermengen zählt.

3. Einheitlicher Rahmen:
   Der Artikel vereinheitlicht die Behandlung dieser Statistiken, indem er zeigt, dass jede auf Kompositionen anwendbare Statistik, die über die Bijektion zu $S_k$ ausdrückbar ist, unter Verwendung der bekannten gemeinsamen Verteilungen von Permutationsstatistiken analysiert werden kann. Dies umfasst die gemeinsame Verteilung von Summe, Major-Index und Absteigerzahl.

4. Explizite Werte und OEIS-Verbindungen:
   Der Autor berechnet und listet explizite Werte für $icr(n)$ und $dcr(n)$für$n$ bis 16 auf und liefert Daten, die bestehenden Einträgen in der On-Line Encyclopedia of Integer Sequences (OEIS A189074, A238343, A238344) entsprechen.

Bedeutung
Der Artikel beansprucht Bedeutung primär durch seine Fähigkeit, explizite Ausdrücke für erzeugende Funktionen bereitzustellen, die zuvor nur für spezifische Fälle bekannt waren oder komplexe Inklusions-Exklusions-Prinzipien zu ihrer Herleitung erforderten. Durch die Etablierung einer direkten Verbindung zwischen Kompositionsstatistiken und Permutationsstatistiken über die MacMahon-Bijektion vereinfacht die Arbeit die Herleitung dieser erzeugenden Funktionen.

Der Autor weist darauf hin, dass die Rechenkomplexität beim Extrahieren von Koeffizienten aus den auf Partitionen basierenden Summen mit $n$ exponentiell wächst, die Methode jedoch effizienter bleibt als die brute-force-Enumeration aller $2^{n-1}$ Kompositionen. Die Arbeit dient als umfassende Referenz für die Verteilungen von Inversionen und Absteigern in ganzzahligen Kompositionen und erweitert die Notation und Ergebnisse früherer Forscher wie Heubach et al. und Knopfmacher et al. auf allgemeine $n$, $k$ und $r$.