首页 > 其他分享 >为什么全序集降位和和逆序对在同一长度的排列的分布相同?

为什么全序集降位和和逆序对在同一长度的排列的分布相同?

时间:2023-11-26 18:45:57浏览次数:30  
标签:全序集 Phi 降位 xf alpha pi operatorname gamma 逆序

引入

在 q-analog 中,我们知道:

\[\sum_{p\in S}q^{\operatorname{maj}(p)}=\sum_{p\in S}q^{\tau(p)}=\binom{\sum a_i}{a_1,a_2,\dots,a_n}_q \]

其中 \(S\) 是 \(a_i\) 个 \(i\) 元素(对于所有 \(i\))构成的排列集合。

\[\operatorname{maj}(p)=\sum_{i<\sum a_i}i[p_i>p_{i+1}] \]

为什么前一个等号成立?

问题和约定

假设 \(X\) 为一全序可重集(显然整数满足这个条件),只需证明:

\[\{\tau(p)\mid p\in X^n\}=\{\operatorname{maj}(p)\mid p\in X^n\} \]

转化为构造一双射函数 \(\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)=f_1^{\pi}f_2^{\pi}\dots f_n^{\pi} \]

下面证明 \(\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\)。

我们希望它满足这样的性质::

  1. \(\Phi\) 是双射。
  2. \(\alpha(\Phi(f))=\alpha(f)\)。
  3. \(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\),有:

\[S(\Phi_{n+1}(fx))=\\ =S(\gamma_x(\Phi_n(f)))+r_x\gamma_x(\Phi_n(f))\\ =S(\Phi_n(f))-r_x\Phi_n(f)+r_xf\\ =S(\Phi_n(f))=T(f) \]

否则,\(f\in X^*R_x\)。

\[S(\Phi_{n+1}(fx))\\ =S(\gamma_x(\Phi_n(f)))+r_xf(\texttt{mentioned above})\\ =S(\Phi_n(f))+l_x(\Phi_n(f))+r_xf\\\ =S(\Phi_n(f))+l_xf+r_xf=S(\Phi_n(f))+\operatorname{len}(f)\\ =T(f) \]

完 全 胜 利

标签:全序集,Phi,降位,xf,alpha,pi,operatorname,gamma,逆序
From: https://www.cnblogs.com/british-union/p/awa.html

相关文章

  • 树状数组(2)-- 逆序对计算
    题干引入洛谷P1908LeedCodeLCR170逆序数(和线代中定义一致)在一个数字序列中,后面比前面小的数字个数之和如84591233的逆序数为:6+4+4+4+0+0+0+0=18使用一种办法求出逆序数树状数组解法根据上面序列中的数组出现次数,可以构建如下桶:ID1234567......
  • 输入不多于5位的正整数,输出它的每位数字和它是几位数,并将其按逆序排列
    #include<stdio.h>intmain(){  intm,a,b,c,d,e,i=0;  scanf_s("%d",&m);  a=(int)(m/10000);  b=(int)((m-a*10000)/1000);  c=(int)((m-a*10000-b*1000)/100);  d=(int)((m-a*10000-b*1000-......
  • 关于用逆序数求解行列式的知识都在这里啦
    利用逆序求n阶行列式的值你知道怎么判断一组数字的逆序数吗?你会使用逆序计算这个行列式吗?这个四阶行列式千万不要展开求解......
  • 面试必刷TOP101:20、数组中的逆序对
    题目题解解法一:暴力法importjava.util.*;publicclassSolution{/***代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可***@paramnumsint整型一维数组*@returnint整型*/publicintInversePairs(in......
  • 归并排序统计逆序对的数量
    788.逆序对的数量-AcWing题库 昨天刚好做到这题,发现网上题解都讲的不是很详细,于是决定自己手写一篇。 归并排序能统计逆序对的数量 为什么归并排序能统计逆序对数量???归并排序的特点是,以mid,mid+1为分界,对两边分别进行排序借助递归的性质先将两边都从小到大排好序,之......
  • 归并排序求逆序对
    #include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;constintN=1e5+10;inta[N];intans=0;inttmp[N];voidmergesort(inta[],intl,intr){if(l>=r)return;intmid=l+r>>1;m......
  • 对整数逆序两次,判断是否与原来的值相等
    调用函数的代码:boolisSameAfterReversals(intnum){  intnewans=0,newans2=0,i=num;  if(i<10){    returntrue;  }  while(i>0){      newans=newans*10+i%10;      i/=10;      ......
  • 字符串逆序输出改错(二)(二级指针)
    代码:如下1#include<malloc.h>2#include<stdio.h>34voidgetMemory(intlen,char*p)5{6p=(char*)malloc(len);7}8intmain()9{10charsrc[]="hello,world";11char*dest=NULL;12char*d=NUL......
  • 字符逆序改错题,面试中经常遇到,本人已经遇到两次!!
    题目:请找出下面代码的所有错误,说明:一下代码是把一个字符串倒序,如"abcd"倒序为"dcba",以下是引用的代码1#include"string.h"2main()3{4char*pSrc="hello,world";5char*pDest=NULL;6intiLen=strlen(pSrc);7pDest=(char*)......
  • 整型数组逆序
    整型数组逆序由于int型数组没有实现comparator接口,所以不支持逆序排序,所以我们建数组的时候就建成Integer型就好了Scannerin=newScanner(System.in);inttarget=Integer.parseInt(in.nextLine());String[]split=in.nextLine().split("");Integer[]arr=n......