Distributions of Inversions and Descents over Integer Compositions

Technical Summary: Distributions of Inversions and Descents over Integer Compositions

Problem Statement
The paper addresses the enumeration of integer compositions, specifically focusing on the distribution of two fundamental permutation statistics—inversions and descents—applied to compositions. A $k$-composition of an integer $n$ is defined as an ordered $k$-tuple of positive integers summing to $n$. While previous literature (e.g., Heubach et al., Knopfmacher et al.) had established generating functions for specific cases or asymptotic behaviors of inversion counts in compositions, this work aims to derive explicit generating functions for the general cases:

1. The number of $k$-compositions of $n$ with a specific number of inversions ($icr(n, k)$).
2. The number of $k$-compositions of $n$ with a specific number of descents ($dcr(n, k)$).
3. The corresponding univariate cases where $k$ is unrestricted ($icr(n)$ and $dcr(n)$).

Methodology
The core approach relies on a bijective mapping between the set of $k$-compositions ($C_k$) and pairs consisting of a permutation ($\pi \in S_k$) and an integer partition ($\lambda$). This bijection, attributed to MacMahon, associates a composition $\sigma$ with a unique permutation $\pi$ (which sorts the parts of $\sigma$ in weakly decreasing order with specific tie-breaking rules) and a partition $\lambda$ such that:
$$|\sigma| = |\lambda| + \text{maj}(\pi)$$
where $|\cdot|$ denotes the sum of parts and $\text{maj}$ denotes the major index.

The author leverages this bijection to demonstrate that statistics on compositions are directly encoded by corresponding statistics on the associated permutations. Specifically:

• The inversion number of a composition $\sigma$ corresponds to the inversion number of the associated permutation $\pi$.
• The descent number of $\sigma$ relates to the descent number of the inverse permutation $\pi^{-1}$ (or equivalently, the major index of $\pi$ via the Foata bijection).
• The comajor index of $\sigma$ corresponds to the inverse major index of $\pi$.

By utilizing known generating functions for joint statistics over the symmetric group $S_k$—specifically the distribution of $(\text{maj}, \text{inv})$ and $(\text{inv}, \text{des})$—the paper translates these results into generating functions for compositions. The derivation involves standard $q$-analog notation, Gaussian binomial coefficients, and Schur functions.

Key Contributions and Results

1. General Generating Functions for Inversions:
   The paper derives a bivariate generating function for the number of $k$-compositions of $n$ with $r$ inversions. Theorem 10 establishes that the distribution of inversions over $C_k$ is related to the distribution of $(\text{maj}, \text{inv})$ over $S_k$.

   • Corollary 11 provides the explicit generating function $IC_q(p, k)$ in terms of a sum over partitions $\lambda \vdash k$ involving $f^\lambda(p)f^\lambda(q)$, where $f^\lambda(q)$ is the $q$-analog of the number of standard Young tableaux of shape $\lambda$.
   • A recurrence relation for $IC_q(p, k)$ is also provided, allowing for the computation of coefficients without summing over all partitions.

2. General Generating Functions for Descents:
   Similarly, the paper derives the generating function for the number of $k$-compositions with a given number of descents.

   • Corollary 12 expresses the generating function $DC_t(q, k)$ using the $q$-Eulerian polynomials $A_k(q, t)$, which describe the distribution of $(\text{inv}, \text{des})$ over $S_k$.
   • The result is given as a sum over partitions involving the statistic $g_\lambda(q)$, which counts tableaux weighted by descent sets.

3. Unified Framework:
   The paper unifies the treatment of these statistics by showing that any statistic on compositions expressible via the bijection to $S_k$ can be analyzed using the known joint distributions of permutation statistics. This includes the joint distribution of sum, major index, and descent number.

4. Explicit Values and OEIS Connections:
   The author computes and lists explicit values for $icr(n)$ and $dcr(n)$ for $n$ up to 16, providing data that corresponds to existing entries in the On-Line Encyclopedia of Integer Sequences (OEIS A189074, A238343, A238344).

Significance
The paper claims significance primarily in its ability to provide explicit expressions for generating functions that were previously only known for specific cases or required complex inclusion-exclusion principles to derive. By establishing a direct link between composition statistics and permutation statistics via the MacMahon bijection, the work simplifies the derivation of these generating functions.

The author notes that while the computational complexity of extracting coefficients from the partition-based sums grows exponentially with $n$, the method remains more efficient than brute-force enumeration of all $2^{n-1}$ compositions. The work serves as a comprehensive reference for the distributions of inversions and descents in integer compositions, extending the notation and results of previous researchers like Heubach et al. and Knopfmacher et al. to general $n$, $k$, and $r$.