Inversion Formulae on Permutations Avoiding 321

Pingge Chen, Zhousheng Mei, Suijie Wang

Abstract


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.


Keywords


Pattern avoidance; Catalan number; Dyck path; Generating function

Full Text: PDF