Inversion formulae on permutations avoiding 321 (Q895062)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Inversion formulae on permutations avoiding 321 |
scientific article |
Statements
Inversion formulae on permutations avoiding 321 (English)
0 references
26 November 2015
0 references
Summary: 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}\binom{n-\frac{\Delta(b)}{2}}{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\,\,\text{and}\,\,b_i\geqslant 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.
0 references
pattern avoidance
0 references
Catalan number
0 references
Dyck path
0 references
generating function
0 references