Distributions of Inversions and Descents over Integer Compositions

技术摘要：整数分拆中逆序数与下降数的分布

问题陈述
本文探讨了整数分拆的计数问题，具体聚焦于应用于分拆的两个基本排列统计量——逆序数和下降数的分布。整数 $n$ 的 $k$-分拆定义为 $k$ 个正整数的有序 $k$-元组，其和为 $n$。尽管先前的文献（例如 Heubach 等人、Knopfmacher 等人）已建立了分拆中逆序数特定情况或渐近行为的生成函数，但本工作旨在推导一般情况的显式生成函数：

1. 具有特定逆序数的 $n$ 的 $k$-分拆的数量（$icr(n, k)$）。
2. 具有特定下降数的 $n$ 的 $k$-分拆的数量（$dcr(n, k)$）。
3. 相应的单变量情形，其中 $k$ 不受限制（$icr(n)$和$dcr(n)$）。

方法论
核心方法依赖于 $k$-分拆集合（$C_k$）与由排列（$\pi \in S_k$）和整数分拆（$\lambda$）组成的对之间的双射映射。这一归因于 MacMahon 的双射将一个分拆 $\sigma$ 关联到一个唯一的排列 $\pi$（该排列按弱递减顺序对 $\sigma$ 的各部分进行排序，并遵循特定的平局打破规则）以及一个分拆 $\lambda$，使得：
$$|\sigma| = |\lambda| + \text{maj}(\pi)$$
其中 $|\cdot|$ 表示各部分之和，$\text{maj}$ 表示主指标。

作者利用这一双射证明了分拆上的统计量直接由关联排列上的相应统计量编码。具体而言：

• 分拆 $\sigma$ 的逆序数对应于关联排列 $\pi$ 的逆序数。
• $\sigma$ 的下降数与逆排列 $\pi^{-1}$ 的下降数相关（或者等价地，通过 Foata 双射与 $\pi$ 的主指标相关）。
• $\sigma$ 的余主指标对应于 $\pi$ 的逆主指标。

通过利用对称群 $S_k$ 上联合统计量的已知生成函数——特别是 $(\text{maj}, \text{inv})$ 和 $(\text{inv}, \text{des})$ 的分布——本文将这些结果转化为分拆的生成函数。推导过程涉及标准的 $q$-模拟记号、高斯二项式系数和 Schur 函数。

主要贡献与结果

1. 逆序数的通用生成函数：
   本文推导了具有 $r$ 个逆序数的 $n$ 的 $k$-分拆数量的双变量生成函数。定理 10 确立了 $C_k$ 上逆序数的分布与 $S_k$ 上 $(\text{maj}, \text{inv})$ 分布之间的关系。

   • 推论 11 提供了显式生成函数 $IC_q(p, k)$，其表示为对分拆 $\lambda \vdash k$ 求和的形式，涉及 $f^\lambda(p)f^\lambda(q)$，其中 $f^\lambda(q)$ 是形状为 $\lambda$ 的标准杨表数量的 $q$-模拟。
   • 同时也提供了 $IC_q(p, k)$ 的递推关系，使得无需对所有分拆求和即可计算系数。

2. 下降数的通用生成函数：
   同样，本文推导了具有给定下降数的 $k$-分拆数量的生成函数。

   • 推论 12 使用 $q$-欧拉多项式 $A_k(q, t)$ 表达了生成函数 $DC_t(q, k)$，该多项式描述了 $S_k$ 上 $(\text{inv}, \text{des})$ 的分布。
   • 结果表示为对涉及统计量 $g_\lambda(q)$ 的分拆求和的形式，该统计量按下降集对杨表进行加权计数。

3. 统一框架：
   本文通过展示任何可通过与 $S_k$ 的双射表达的分拆统计量均可利用排列统计量的已知联合分布进行分析，统一了这些统计量的处理。这包括和、主指标以及下降数的联合分布。

4. 显式值与 OEIS 关联：
   作者计算并列举了 $n$ 直至 16 的 $icr(n)$和$dcr(n)$ 的显式值，提供了对应于在线整数序列百科全书（OEIS A189074, A238343, A238344）中现有条目的数据。

意义
本文的主要意义在于能够提供显式表达式的生成函数，这些函数此前仅针对特定情况已知，或需要复杂的容斥原理来推导。通过建立分拆统计量与排列统计量之间经由 MacMahon 双射的直接联系，这项工作简化了这些生成函数的推导过程。

作者指出，虽然从基于分拆的求和中提取系数的计算复杂度随 $n$ 呈指数级增长，但该方法仍比暴力枚举所有 $2^{n-1}$ 个分拆更为高效。本文作为整数分拆中逆序数和下降数分布的综合参考，将 Heubach 等人及 Knopfmacher 等人等先前研究者的记号和结果推广至一般的 $n$、$k$ 和 $r$。