Unlabeled $2 2$-free posets, ascent sequences and pattern avoiding permutationsReport as inadecuate




Unlabeled $2 2$-free posets, ascent sequences and pattern avoiding permutations - Download this document for free, or read online. Document in PDF available to download.

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique 2 School of Computer Science - The Mathematics Institute, Reyjavik University 3 Science Institute, University of Iceland 4 Reykjavik University - Institute of Mathematics

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.

Résumé : Nous présentons des bijections, transportant de nombreuses statistiques, entre quatre classes d-objets. Deux d-entre elles, la classe des EPO ensembles partiellement ordonnés sans motif $\textrm{2+2}$ et une certaine classe d-involutions, sont déjà apparues dans la littérature. La troisième est une classe de permutations à motifs exclus, et la quatrième une classe de suites que nous appelons $\textit{suites à montées}$. Nous déterminons ensuite la série génératrice de ces classes, retrouvant ainsi un résultat prouvé par Zagier pour les involutions sus-mentionnées. La série obtenue n-est pas D-finie. Apparemment, le fait qu-elle compte aussi les EPO sans motif $\textrm{2+2}$ est nouveau. Finalement, nous caractérisons les suites à montées qui correspondent aux permutations évitant le motif barré $3\bar{1}52\bar{4}$ et énumérons ces permutations, ce qui démontre une conjecture de Pudwell.

Keywords : $\mathrm{2+2}$-free poset interval order pattern-avoidance enumeration ascent sequence kernel method





Author: Mireille Bousquet-Mélou - Anders Claesson - Mark Dukes - Sergey Kitaev -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents