Inversion Formulae on Permutations Avoiding 321

  • Pingge Chen
  • Zhousheng Mei
  • Suijie Wang
Keywords: Pattern avoidance, Catalan number, Dyck path, Generating function


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.

Article Number