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

https://hal.inria.fr/hal-00396372
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 11:08:35 AM
Last modification on : Wednesday, December 30, 2020 - 1:56:02 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:48:29 AM

File

dmAK0118.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-00396372, version 2

Collections

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. ⟨hal-00396372v2⟩

Share

Metrics

Record views

158

Files downloads

733