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

Summary: 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\cdots 21)\) patterns that occur in \(\sigma\) in terms of the corresponding Dyck path.