An area-to-inv bijection between Dyck paths and 312-avoiding permutations (Q5954313): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Latest revision as of 00:48, 5 March 2024
scientific article; zbMATH DE number 1699538
Language | Label | Description | Also known as |
---|---|---|---|
English | An area-to-inv bijection between Dyck paths and 312-avoiding permutations |
scientific article; zbMATH DE number 1699538 |
Statements
An area-to-inv bijection between Dyck paths and 312-avoiding permutations (English)
0 references
7 February 2002
0 references
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.
0 references
Catalan polynomial
0 references
Dyck paths
0 references
Catalan number
0 references
312-avoiding permutations
0 references
inversion statistic
0 references