Mireille Bousquet-Mélou ; Anders Claesson ; Mark Dukes ; Sergey Kitaev - Unlabeled $(2+2)$-free posets, ascent sequences and pattern avoiding permutations

dmtcs:2723 - Discrete Mathematics & Theoretical Computer Science, January 1, 2009, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) - https://doi.org/10.46298/dmtcs.2723
Unlabeled $(2+2)$-free posets, ascent sequences and pattern avoiding permutations

Authors: Mireille Bousquet-Mélou ORCID-iD1; Anders Claesson 2; Mark Dukes ORCID-iD3,4; Sergey Kitaev ORCID-iD5

  • 1 Laboratoire Bordelais de Recherche en Informatique
  • 2 The Mathematics Institute, Reyjavik University
  • 3 Science Institute, University of Iceland
  • 4 University of Iceland [Reykjavik]
  • 5 Institute of Mathematics

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.


Volume: DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
Section: Proceedings
Published on: January 1, 2009
Imported on: January 31, 2017
Keywords: $(\mathrm{2+2})$-free poset,interval order,pattern-avoidance,enumeration,ascent sequence,kernel method,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Structures aléatoires discrètes et algorithmes; Funder: French National Research Agency (ANR); Code: ANR-05-BLAN-0372

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV math/0510676
Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.aam.2005.12.006
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.math/0510676
  • 10.48550/arxiv.math/0510676
  • math/0510676
  • 10.1016/j.aam.2005.12.006
Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes

1 Document citing this article

Consultation statistics

This page has been seen 168 times.
This article's PDF has been downloaded 135 times.