Distributions of Inversions and Descents over Integer Compositions

Resumo Técnico: Distribuições de Inversões e Descidas sobre Composições Inteiras

Declaração do Problema
O artigo aborda a enumeração de composições inteiras, focando especificamente na distribuição de duas estatísticas fundamentais de permutações — inversões e descidas — aplicadas a composições. Uma $k$-composição de um inteiro $n$ é definida como uma $k$-tupla ordenada de inteiros positivos que somam $n$. Embora a literatura anterior (por exemplo, Heubach et al., Knopfmacher et al.) tenha estabelecido funções geradoras para casos específicos ou comportamentos assintóticos de contagens de inversões em composições, este trabalho visa derivar funções geradoras explícitas para os casos gerais:

1. O número de $k$-composições de $n$ com um número específico de inversões ($icr(n, k)$).
2. O número de $k$-composições de $n$ com um número específico de descidas ($dcr(n, k)$).
3. Os casos univariados correspondentes onde $k$ é ilimitado ($icr(n)$e$dcr(n)$).

Metodologia
A abordagem central baseia-se em um mapeamento bijetivo entre o conjunto de $k$-composições ($C_k$) e pares consistindo de uma permutação ($\pi \in S_k$) e uma partição inteira ($\lambda$). Esta bijeção, atribuída a MacMahon, associa uma composição $\sigma$ a uma permutação única $\pi$ (que ordena as partes de $\sigma$ em ordem decrescente fraca com regras específicas de desempate) e uma partição $\lambda$ tal que:
$$|\sigma| = |\lambda| + \text{maj}(\pi)$$
onde $|\cdot|$ denota a soma das partes e $\text{maj}$ denota o índice major.

O autor aproveita esta bijeção para demonstrar que estatísticas sobre composições são diretamente codificadas por estatísticas correspondentes nas permutações associadas. Especificamente:

• O número de inversões de uma composição $\sigma$ corresponde ao número de inversões da permutação associada $\pi$.
• O número de descidas de $\sigma$ relaciona-se ao número de descidas da permutação inversa $\pi^{-1}$ (ou equivalentemente, ao índice major de $\pi$ via a bijeção de Foata).
• O índice comajor de $\sigma$ corresponde ao índice major inverso de $\pi$.

Ao utilizar funções geradoras conhecidas para estatísticas conjuntas sobre o grupo simétrico $S_k$ — especificamente a distribuição de $(\text{maj}, \text{inv})$ e $(\text{inv}, \text{des})$ — o artigo traduz esses resultados em funções geradoras para composições. A derivação envolve notação padrão de $q$-análogos, coeficientes binomiais gaussianos e funções de Schur.

Contribuições e Resultados Principais

1. Funções Geradoras Gerais para Inversões:
   O artigo deriva uma função geradora bivariada para o número de $k$-composições de $n$ com $r$ inversões. O Teorema 10 estabelece que a distribuição de inversões sobre $C_k$ está relacionada à distribuição de $(\text{maj}, \text{inv})$ sobre $S_k$.

   • O Corolário 11 fornece a função geradora explícita $IC_q(p, k)$ em termos de uma soma sobre partições $\lambda \vdash k$ envolvendo $f^\lambda(p)f^\lambda(q)$, onde $f^\lambda(q)$ é o $q$-análogo do número de tabelas de Young padrão de forma $\lambda$.
   • Uma relação de recorrência para $IC_q(p, k)$ também é fornecida, permitindo o cálculo dos coeficientes sem somar sobre todas as partições.

2. Funções Geradoras Gerais para Descidas:
   Da mesma forma, o artigo deriva a função geradora para o número de $k$-composições com um dado número de descidas.

   • O Corolário 12 expressa a função geradora $DC_t(q, k)$ usando os polinômios $q$-Eulerianos $A_k(q, t)$, que descrevem a distribuição de $(\text{inv}, \text{des})$ sobre $S_k$.
   • O resultado é dado como uma soma sobre partições envolvendo a estatística $g_\lambda(q)$, que conta tabelas ponderadas por conjuntos de descidas.

3. Estrutura Unificada:
   O artigo unifica o tratamento dessas estatísticas ao mostrar que qualquer estatística sobre composições expressível via a bijeção para $S_k$ pode ser analisada usando as distribuições conjuntas conhecidas de estatísticas de permutação. Isso inclui a distribuição conjunta de soma, índice major e número de descidas.

4. Valores Explícitos e Conexões com a OEIS:
   O autor calcula e lista valores explícitos para $icr(n)$e$dcr(n)$ para $n$ até 16, fornecendo dados que correspondem a entradas existentes na Enciclopédia Online de Sequências Inteiras (OEIS A189074, A238343, A238344).

Significado
O artigo reivindica significado principalmente em sua capacidade de fornecer expressões explícitas para funções geradoras que anteriormente eram conhecidas apenas para casos específicos ou exigiam princípios complexos de inclusão-exclusão para sua derivação. Ao estabelecer um link direto entre estatísticas de composições e estatísticas de permutações via a bijeção de MacMahon, o trabalho simplifica a derivação dessas funções geradoras.

O autor observa que, embora a complexidade computacional de extrair coeficientes das somas baseadas em partições cresça exponencialmente com $n$, o método permanece mais eficiente que a enumeração por força bruta de todas as $2^{n-1}$ composições. O trabalho serve como uma referência abrangente para as distribuições de inversões e descidas em composições inteiras, estendendo a notação e os resultados de pesquisadores anteriores como Heubach et al. e Knopfmacher et al. para $n$, $k$ e $r$ gerais.