关于利用Foata映射构造满足comaj(σ)=inv(coΦ(σ))的Sₙ上双射coΦ的问题咨询

嗨，我看到你在利用Foata映射推导$co\Phi$的时候卡住了，主要是一开始对$\operatorname{comaj}$的代数变形出错了——你把$\sum_{\sigma_i>\sigma_{i+1}}(n-i)$写成了$n - \sum_{\sigma_i>\sigma_{i+1}}i$，这里的问题在于$n$要乘以下降位置的数量，而不是只减一次，正确的变形应该是：

$$\operatorname{comaj}(\sigma) = \sum_{\sigma_i>\sigma_{i+1}}(n-i) = n \cdot d(\sigma) - \operatorname{maj}(\sigma)$$

其中$d(\sigma)$是$\sigma$的下降位置总数（也就是满足$\sigma_i>\sigma_{i+1}$的$i$的个数）。不过其实我们可以换个更直接的角度，结合反转置换和Foata映射的性质来构造$co\Phi$。

第一步：理清$\operatorname{comaj}$和$\operatorname{maj}$的关系（借助反转置换） #

先定义反转置换：对于$\sigma \in S_n$，它的反转$\sigma^{R$满足$\sigma}R(k) = \sigma(n+1-k)$（也就是把$\sigma$的元素从后往前倒过来写）。

我们可以推导$\operatorname{comaj}(\sigma)$和$\operatorname{maj}(\sigma^R)$的关系：

• 对于$\sigma$的每个下降位置$i$（即$\sigma_i>\sigma_{i+1}$），对应到$\sigma^R$中，位置$k = n-i$是一个上升位置（即$\sigma^R(k) < \sigma^R(k+1)$）。
• 所有1到$n-1$的位置的和是$\frac{n(n-1)}{2}$，而上升位置的和等于这个总和减去下降位置的和（也就是$\operatorname{maj}(\sigma^R)$）。

所以：
$$\operatorname{comaj}(\sigma) = \sum_{\sigma的下降位置i} (n-i) = \sum_{\sigma^R的上升位置k} k = \frac{n(n-1)}{2} - \operatorname{maj}(\sigma^R)$$

第二步：结合Foata映射的性质 #

你已经知道Foata映射$\Phi$是$S_n$上的双射，并且满足$\operatorname{maj}(\tau) = \operatorname{inv}(\Phi(\tau))$对任意$\tau \in S_n$。

现在我们需要把$\operatorname{comaj}(\sigma)$转化为某个置换的逆序数：

• 代入上面的等式，得到$\operatorname{comaj}(\sigma) = \frac{n(n-1)}{2} - \operatorname{inv}(\Phi(\sigma^R))$。
• 这里有个关键性质：对于任意置换$\tau$，它的反转置换$\tau^{R$的逆序数满足$\operatorname{inv}(\tau}R) = \frac{n(n-1)}{2} - \operatorname{inv}(\tau)$（因为反转置换会把原置换的逆序对和非逆序对互换，总可能的逆序对数量是$\frac{n(n-1)}{2}$）。

把这个性质代入，就能得到：
$$\operatorname{comaj}(\sigma) = \operatorname{inv}\left( \left( \Phi(\sigma^R) \right)^R \right)$$

第三步：定义双射$co\Phi$ #

我们直接定义：
$$co\Phi(\sigma) = \left( \Phi(\sigma^R) \right)^R$$

现在验证这个映射的性质：

• 双射性：反转置换是$S_n$上的双射，Foata映射$\Phi$也是双射，双射的复合仍然是双射，所以$co\Phi$是$S_n$上的双射。
• 满足$\operatorname{comaj}(\sigma) = \operatorname{inv}(co\Phi(\sigma))$：上面的推导已经直接证明了这一点。

补充验证（举个小例子） #

比如取$n=3$，$\sigma=[2,1,3]$：

• $\sigma$的下降位置是$i=1$，$\operatorname{comaj}(\sigma)=3-1=2$。
• $\sigma^{R=[3,1,2]$，$\operatorname{maj}(\sigma}R)=1$（下降位置是$i=1$）。
• $\Phi(\sigma^{R)$是满足$\operatorname{inv}(\Phi(\sigma}R))=1$的置换，比如$\Phi(\sigma^R)=[1,3,2]$（逆序数是1）。
• $co\Phi(\sigma)=([1,3,2])^R=[2,3,1]$，它的逆序数是2，正好等于$\operatorname{comaj}(\sigma)$，符合要求。

备注：内容来源于stack exchange，提问作者V. Isidore