引入
在 q-analog 中，我们知道：
其中 \(S\) 是 \(a_i\) 个 \(i\) 元素（对于所有 \(i\)）构成的排列集合。
为什么前一个等号成立？
问题和约定
假设 \(X\) 为一全序可重集（显然整数满足这个条件），只需证明：
转化为构造一双射函数 \(\Phi_n\mapsto X^n\to X^n\)。
下面做若干符号的约定。
设 \(f=x_1x_2\dots x_n\) 是一 \(X\) 的字。
定义 \(L_xf=\{w\mid w\in f\le x\},R_xf=\{w\mid w\in f> x\}\)，明确时略去 \(f\)。
\(l_xf=|L_xf|,r_xf=|R_xf|\)，\(\operatorname{len}(f)=n\)。
\(S(f)=\tau(f),T(f)=\operatorname{maj}(f)\)。
对于，两字母表 \(X,Y\)，定义 \(XY=\{xy\mid x\in X,y\in Y\}\)。
\(f^{\pi}\) 为一一元运算， \(f^{\pi}=x_nx_1x_2\dots x_{n-1}\)。
若 \(\forall x\in X,l_xf_1=l_xf_2\)，那么记为 \(\alpha(f_1)=\alpha(f_2)\)。注意此时也有 \(r_xf_1=r_xf_2\)。
证明
显然，对于任意\(x\in X\)，\(\{X^*L_x,X^*R_x\}\) 是对 \(X^*X\) 的划分。
设 \(f=x_1x_2\dots x_n\) 是任一 \(X\) 的长度为 \(n\) 的字 。
若 \(f\in X^*L_x\)，定义序列 \([r_1,r_2,\dots,r_s]\) 为 \(f\) 中所有属于 \(L_x\) 的下标的升序序列。
否则（\(f\in X^*R_x\)），定义序列 \([r_1,r_2,\dots,r_s]\) 为 \(f\) 中所有属于 \(R_x\) 的下标的升序序列。
特殊地，\(r_0=0,r_{s+1}=n+1\)。
分解 \(f\) 为 \(f_1f_2\dots f_s\)，其中 \(f_p=x[r_{p-1}+1:r_p]\)。显然，这样的分解是唯一的。
对于 \(f\in X^*L_x\)，显然有 \(f_p\in R_x^*L_x\)，否则 \(f_p\in L_x^*R_x\)。
定义 \(\gamma_x\mapsto X^*\to X^*(x\in X)\) ，构造方式为：
下面证明 \(\gamma_x\) 是双射：
考虑 \(f\) 到 \(\gamma_x(f)\)，由于分解唯一，不同的分解每一项做一下 \(f^\pi\) 过来也不同，所以不同的 \(f\) 对应 \(\gamma_x(f)\) 不同。
显然 \(\{L_xX^*,R_xX^*\}\) 也是对 \(X^*X\) 的划分。
同样像上面定义分解，只不过 \(f_p=x[r_p:r_{p+1}-1]\)。这样的分解显然也是唯一的。
由于 \(f_p\in L_xX^*\)（\(f_p\in R_xX^*\)），\(f_p^{\pi}\in X^*L_x\)（\(f_p^{\pi}\in X^*R_x\)），所以 \(\gamma_x(f)\) 到 \(f\) 可以看作以这样的方式分解再做 \(f^{\pi}\)，显然也是不同的。所以不同的 \(\gamma_x(f)\) 对应不同的 \(f\)。
由于 \(\gamma_x\) 不过是打乱了 \(f\) 的顺序，显然 \(\alpha(\gamma_x(f))=\alpha(f)\)。
接下来我们考察逆序对、降位和的若干性质。
下面 \(f\in X^*,x\in X\)。
Lemma 1：\(S(fx)=S(f)+r_xf\)。
由逆序对定义，显然；
Lemma 2：\(S(\gamma_x(f))=S(f)-r_xf\ (\text{if }f\in X^*L_x)\)
考虑分解成若干 \(f_p\) 块，块间贡献不变，块内的 \(R_x^*L_x\) 变成了 \(L_xR_x^*\)，\(R_x^*\) 内部的逆序对不改变，只有 \(L_x\) 和 \(R_x^*\) 之间的逆序对改变了。由于其偏序关系，减少了 \(r_x\) 个逆序对。减少的总逆序对是 \(\sum r_x f_p=r_xf\)。
Lemma 3：\(S(\gamma_x(f))=S(f)+l_xf\ (\text{if }f\in X^*R_x)\)
同理。
Lemma 4：\(T(fx)=T(f)\ (\text{if }f\in X^*L_x)\)
显然，不会增加任何降位。
Lemma 5：\(T(fx)=T(f)+\operatorname{len}(f)\ (\text{if }f\in X^*R_x)\)
增加了最后一个位置，下标是 \(\operatorname{len}(f)\)。
下面我们构造我们希望得到的双射函数 \(\Phi(f)\mapsto X^*\to X^*\)。
把 \(\Phi(f)\) 记为 \(\Phi_n(f)\)，其中 \(\operatorname{len}(f)=n\)。
我们希望它满足这样的性质：：
- \(\Phi\) 是双射。
- \(\alpha(\Phi(f))=\alpha(f)\)。
- \(S(\Phi(f))=T(f)\)。
如此可满足要求。
给出其构造方式：
\(\Phi(f)=f\ (\text{if }\operatorname{len}(f)=1)\)
\(\Phi(fx)=\gamma_x(\Phi(f))x\ (\text{otherwise})\)
下面证明其满足这些性质。
归纳法，假设 \(\Phi_n\) 满足。\(n=1\) 时显然满足。
由于双射函数的复合是双射， \(\gamma_x(\Phi_n(f))\) 是双射，且 \(\alpha(\gamma_x(\Phi_n(f)))=\alpha(f)\)。
因此 \(fx\to \Phi_{n+1}(fx)=\gamma_x(\Phi(f))x\) 是双射，即证明了 \(\Phi_{n+1}(f)\) 是双射。
由于 \(\Phi_{n}\) 只不过是打乱了顺序，所以 \(\Phi_{n+1}\) 只不过是打乱了顺序，所以 \(\alpha(\Phi_{n+1}(f))=\alpha(f)\)。
下面证明最后一条要求。
若 \(f\in X^*L_x\)，则依构造得到 \(\Phi_{n+1}(f)\in X^*L_x\)，有：
否则，\(f\in X^*R_x\)。
完 全 胜 利