HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Unlabeled $(2+2)$-free posets, ascent sequences and pattern avoiding permutations

Abstract : We present statistic-preserving bijections between four classes of combinatorial objects. Two of them, the class of unlabeled $(\textrm{2+2})$-free posets and a certain class of chord diagrams (or involutions), already appeared in the literature, but were apparently not known to be equinumerous. The third one is a new class of pattern avoiding permutations, and the fourth one consists of certain integer sequences called $\textit{ascent sequences}$. We also determine the generating function of these classes of objects, thus recovering a non-D-finite series obtained by Zagier for chord diagrams. Finally, we characterize the ascent sequences that correspond to permutations avoiding the barred pattern $3\bar{1}52\bar{4}$, and enumerate those permutations, thus settling a conjecture of Pudwell.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 11:08:35 AM
Last modification on : Monday, December 20, 2021 - 4:50:12 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:48:29 AM


Publisher files allowed on an open archive




Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes, Sergey Kitaev. Unlabeled $(2+2)$-free posets, ascent sequences and pattern avoiding permutations. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. pp.217-228, ⟨10.46298/dmtcs.2723⟩. ⟨hal-00396372v2⟩



Record views


Files downloads