Inversion Formulae on Permutations Avoiding 321
Inversion Formulae on Permutations Avoiding 321
复制标题
DOI：
10.37236/5451
复制
发表时间：
2015-11
期刊：
影响因子：
--
通讯作者：
Pingge Chen;Zhousheng Mei;Suijie Wang
中科院分区：
文献类型：
--
作者：
Pingge Chen;Zhousheng Mei;Suijie Wang
我们将研究$321$避免置换的逆统计量，得到$[n]$上具有$m$逆的$321$避免置换的个数由[|\mathcal{S}_{n，m}(321)|=\sum_{b\vdash m}{n-\frac{\Delta(B)}{2}\Choose L(B)}给出。其中，求和遍历$m$的所有组成$b=(b_1，b_2，\ldots，b_k)$，即\[m=b_1+b_2+\cdots+b_k\quad{\rm and}\quad b_i\ge 1，\]$L(B)=k$是$b$的长度，$\Delta(b)：=|b_1|+|b_2-b_1|+\cdots+|b_k-b_{k-1}|+|b_k|$.我们得到了一个新的从$321$-避免排列到Dyck路的双射，它建立了$321$-避免排列的倒数与Dyck路的谷高的关系。
We will study the inversion statistic of $321$-avoiding permutations, and obtain that the number of $321$-avoiding permutations on $[n]$ with $m$ inversions is given by \[ |\mathcal {S}_{n,m}(321)|=\sum_{b \vdash m}{n-\frac{\Delta(b)}{2}\choose l(b)}. \] where the sum runs over all compositions $b=(b_1,b_2,\ldots,b_k)$ of $m$, i.e., \[ m=b_1+b_2+\cdots+b_k \quad{\rm and}\quad b_i\ge 1, \] $l(b)=k$ is the length of $b$, and $\Delta(b):=|b_1|+|b_2-b_1|+\cdots+|b_k-b_{k-1}|+|b_k|$. We obtain a new bijection from $321$-avoiding permutations to Dyck paths which establishes a relation on inversion number of $321$-avoiding permutations and valley height of Dyck paths.