hal-00353913, version 1
(2+2)-free posets, ascent sequences and pattern avoiding permutations
Journal of Combinatorial Theory, Series A 117, 7 (2010) 884-909
Résumé : 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.
- 1 :
- CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II
- 2 :
- Reyjavik University
- 3 :
- University of Iceland
- Domaine : Mathématiques/Combinatoire
- Mots-clés : pattern-avoiding permutations – 2+2-free posets – bijections – enumeration
- hal-00353913, version 1
- http://hal.archives-ouvertes.fr/hal-00353913
- oai:hal.archives-ouvertes.fr:hal-00353913
- Contributeur :
- Soumis le : Vendredi 16 Janvier 2009, 18:43:51
- Dernière modification le : Vendredi 20 Juillet 2012, 12:57:05



Documents associés

Exporter