21734 articles – 15570 Notices  [english version]

hal-00353913, version 1

(2+2)-free posets, ascent sequences and pattern avoiding permutations

Mireille Bousquet-Mélou () 1, Anders Claesson 2, Mark Dukes 3, Sergey Kitaev 2

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 :  Laboratoire Bordelais de Recherche en Informatique (LaBRI)
  • 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 :  The Mathematics Institute, Reyjavik University
  • Reyjavik University
  • 3 :  Science Institute, University of Iceland
  • University of Iceland
  • Domaine : Mathématiques/Combinatoire
  • Mots-clés : pattern-avoiding permutations – 2+2-free posets – bijections – enumeration
 
  • hal-00353913, version 1
  • 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