Distributions of Inversions and Descents over Integer Compositions

Resumen Técnico: Distribuciones de Inversiones y Descensos sobre Composiciones Enteras

Enunciado del Problema
El artículo aborda la enumeración de composiciones enteras, centrándose específicamente en la distribución de dos estadísticas fundamentales de permutaciones —inversiones y descensos— aplicadas a composiciones. Una $k$-composición de un entero $n$ se define como una $k$-tupla ordenada de enteros positivos que suman $n$. Aunque la literatura previa (por ejemplo, Heubach et al., Knopfmacher et al.) había establecido funciones generadoras para casos específicos o comportamientos asintóticos de los recuentos de inversiones en composiciones, este trabajo tiene como objetivo derivar funciones generadoras explícitas para los casos generales:

1. El número de $k$-composiciones de $n$ con un número específico de inversiones ($icr(n, k)$).
2. El número de $k$-composiciones de $n$ con un número específico de descensos ($dcr(n, k)$).
3. Los casos univariados correspondientes donde $k$ es ilimitado ($icr(n)$y$dcr(n)$).

Metodología
El enfoque central se basa en una aplicación biyectiva entre el conjunto de $k$-composiciones ($C_k$) y pares formados por una permutación ($\pi \in S_k$) y una partición entera ($\lambda$). Esta biyección, atribuida a MacMahon, asocia una composición $\sigma$ con una permutación única $\pi$ (que ordena las partes de $\sigma$ en orden débilmente decreciente con reglas específicas de desempate) y una partición $\lambda$ tal que:
$$|\sigma| = |\lambda| + \text{maj}(\pi)$$
donde $|\cdot|$ denota la suma de las partes y $\text{maj}$ denota el índice mayor.

El autor aprovecha esta biyección para demostrar que las estadísticas sobre composiciones están codificadas directamente por las estadísticas correspondientes sobre las permutaciones asociadas. Específicamente:

• El número de inversiones de una composición $\sigma$ corresponde al número de inversiones de la permutación asociada $\pi$.
• El número de descensos de $\sigma$ se relaciona con el número de descensos de la permutación inversa $\pi^{-1}$ (o equivalentemente, con el índice mayor de $\pi$ mediante la biyección de Foata).
• El índice comayor de $\sigma$ corresponde al índice mayor inverso de $\pi$.

Mediante el uso de funciones generadoras conocidas para estadísticas conjuntas sobre el grupo simétrico $S_k$ —específicamente la distribución de $(\text{maj}, \text{inv})$ y $(\text{inv}, \text{des})$—, el artículo traduce estos resultados en funciones generadoras para composiciones. La derivación involucra notación estándar de $q$-análogos, coeficientes binomiales gaussianos y funciones de Schur.

Contribuciones y Resultados Clave

1. Funciones Generadoras Generales para Inversiones:
   El artículo deriva una función generadora bivariada para el número de $k$-composiciones de $n$ con $r$ inversiones. El Teorema 10 establece que la distribución de inversiones sobre $C_k$ está relacionada con la distribución de $(\text{maj}, \text{inv})$ sobre $S_k$.

   • El Corolario 11 proporciona la función generadora explícita $IC_q(p, k)$ en términos de una suma sobre particiones $\lambda \vdash k$ que involucra $f^\lambda(p)f^\lambda(q)$, donde $f^\lambda(q)$ es el $q$-análogo del número de tablas de Young estándar de forma $\lambda$.
   • También se proporciona una relación de recurrencia para $IC_q(p, k)$, lo que permite el cálculo de coeficientes sin sumar sobre todas las particiones.

2. Funciones Generadoras Generales para Descensos:
   De manera similar, el artículo deriva la función generadora para el número de $k$-composiciones con un número dado de descensos.

   • El Corolario 12 expresa la función generadora $DC_t(q, k)$ utilizando los polinomios $q$-eulerianos $A_k(q, t)$, que describen la distribución de $(\text{inv}, \text{des})$ sobre $S_k$.
   • El resultado se presenta como una suma sobre particiones que involucra la estadística $g_\lambda(q)$, que cuenta tablas ponderadas por conjuntos de descensos.

3. Marco Unificado:
   El artículo unifica el tratamiento de estas estadísticas al mostrar que cualquier estadística sobre composiciones expresable mediante la biyección a $S_k$ puede analizarse utilizando las distribuciones conjuntas conocidas de estadísticas de permutaciones. Esto incluye la distribución conjunta de la suma, el índice mayor y el número de descensos.

4. Valores Explícitos y Conexiones con OEIS:
   El autor calcula y enumera valores explícitos para $icr(n)$y$dcr(n)$ para $n$ hasta 16, proporcionando datos que corresponden a entradas existentes en la Enciclopedia en Línea de Secuencias de Enteros (OEIS A189074, A238343, A238344).

Significado
El artículo reclama importancia principalmente por su capacidad para proporcionar expresiones explícitas para funciones generadoras que anteriormente solo se conocían para casos específicos o requerían principios complejos de inclusión-exclusión para su derivación. Al establecer un vínculo directo entre estadísticas de composiciones y estadísticas de permutaciones mediante la biyección de MacMahon, el trabajo simplifica la derivación de estas funciones generadoras.

El autor señala que, aunque la complejidad computacional de extraer coeficientes de las sumas basadas en particiones crece exponencialmente con $n$, el método sigue siendo más eficiente que la enumeración por fuerza bruta de todas las $2^{n-1}$ composiciones. El trabajo sirve como una referencia exhaustiva para las distribuciones de inversiones y descensos en composiciones enteras, extendiendo la notación y los resultados de investigadores anteriores como Heubach et al. y Knopfmacher et al. a $n$, $k$ y $r$ generales.