HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [11 references]

https://hal.inria.fr/hal-00396372
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

### File

dmAK0118.pdf
Publisher files allowed on an open archive

### Citation

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