An area-to-inv bijection between Dyck paths and 312-avoiding permutations

Jason Bandlow ; Kendra Killpatrick

The electronic journal of combinatorics, Tome 8 (2001) no. 1

Résumé

The symmetric $q,t$-Catalan polynomial $C_n(q,t)$, which specializes to the Catalan polynomial $C_n(q)$ when $t=1$, was defined by Garsia and Haiman in 1994. In 2000, Garsia and Haglund described statistics $a(\pi)$ and $b(\pi)$ on Dyck paths such that $C_n(q,t) = \sum_{\pi} q^{a(\pi)}t^{b(\pi)}$ where the sum is over all $n \times n$ Dyck paths. Specializing $t=1$ gives the Catalan polynomial $C_n(q)$ defined by Carlitz and Riordan and further studied by Carlitz. Specializing both $t=1$ and $q=1$ gives the usual Catalan number $C_n$. The Catalan number $C_n$ is known to count the number of $n \times n$ Dyck paths and the number of $312$-avoiding permutations in $S_n$, as well as at least 64 other combinatorial objects. In this paper, we define a bijection between Dyck paths and $312$-avoiding permutations which takes the area statistic $a(\pi)$ on Dyck paths to the inversion statistic on $312$-avoiding permutations. The inversion statistic can be thought of as the number of $(21)$ patterns in a permutation $\sigma$. We give a characterization for the number of $(321)$, $(4321)$, $\dots$, $(k\cdots21)$ patterns that occur in $\sigma$ in terms of the corresponding Dyck path.

Détail

DOI : 10.37236/1584

Classification : 05A15, 05A19
Mots-clés : Catalan polynomial, Dyck paths, Catalan number, 312-avoiding permutations, inversion statistic