(2+2)-free posets, ascent sequences and pattern avoiding permutations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2008
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916968284553216 |
|---|---|
| author | Bousquet-Mélou, Mireille Claesson, Anders Dukes, Mark Kitaev, Sergey |
| author_facet | Bousquet-Mélou, Mireille Claesson, Anders Dukes, Mark Kitaev, Sergey |
| contents | We present bijections between four classes of combinatorial objects. Two of them, the class of unlabeled (2+2)-free posets and a certain class of involutions (or chord diagrams), already appeared in the literature, but were apparently not known to be equinumerous. We present a direct bijection between them. The third class is a family of permutations defined in terms of a new type of pattern. An attractive property of these patterns is that, like classical patterns, they are closed under the action of $D_8$, the symmetry group of the square. The fourth class is formed by certain integer sequences, called ascent sequences, which have a simple recursive structure and are shown to encode (2+2)-free posets and permutations. Our bijections preserve numerous statistics.
We determine the generating function of these classes of objects, thus recovering a non-D-finite series obtained by Zagier for the class of chord diagrams. Finally, we characterize the ascent sequences that correspond to permutations avoiding the barred pattern $3{\bar 1}52{\bar 4}$ and use this to enumerate those permutations, thereby settling a conjecture of Pudwell. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_0806_0666 |
| institution | arXiv |
| publishDate | 2008 |
| record_format | arxiv |
| spellingShingle | (2+2)-free posets, ascent sequences and pattern avoiding permutations Bousquet-Mélou, Mireille Claesson, Anders Dukes, Mark Kitaev, Sergey Combinatorics We present bijections between four classes of combinatorial objects. Two of them, the class of unlabeled (2+2)-free posets and a certain class of involutions (or chord diagrams), already appeared in the literature, but were apparently not known to be equinumerous. We present a direct bijection between them. The third class is a family of permutations defined in terms of a new type of pattern. An attractive property of these patterns is that, like classical patterns, they are closed under the action of $D_8$, the symmetry group of the square. The fourth class is formed by certain integer sequences, called ascent sequences, which have a simple recursive structure and are shown to encode (2+2)-free posets and permutations. Our bijections preserve numerous statistics. We determine the generating function of these classes of objects, thus recovering a non-D-finite series obtained by Zagier for the class of chord diagrams. Finally, we characterize the ascent sequences that correspond to permutations avoiding the barred pattern $3{\bar 1}52{\bar 4}$ and use this to enumerate those permutations, thereby settling a conjecture of Pudwell. |
| title | (2+2)-free posets, ascent sequences and pattern avoiding permutations |
| topic | Combinatorics |
| url | https://arxiv.org/abs/0806.0666 |