CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Enumerating permutations avoiding a pair of Babson-Steingrimsson patterns

Anders Claesson (Institutionen för matematiska vetenskaper) ; Toufik Mansour
Ars Combinatoria (0381-7032). Vol. 77 (2005), p. 17-31.
[Artikel, refereegranskad vetenskaplig]

Babson and Steingrimsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. Subsequently, Claesson presented a complete solution for the number of permutations avoiding any single pattern of type (1, 2) or (2, 1). For eight of these twelve patterns the answer is given by the Bell numbers. For the remaining four the answer is given by the Catalan numbers. In the present paper we give a complete solution for the number of permutations avoiding a pair of patterns of type (1, 2) or (2, 1). We also conjecture the number of permutations avoiding the patterns in any set of three or more such patterns.

Nyckelord: permutation, pattern avoidance



Denna post skapades 2010-02-25.
CPL Pubid: 114815

 

Institutioner (Chalmers)

Institutionen för matematiska vetenskaperInstitutionen för matematiska vetenskaper (GU)

Ämnesområden

Matematik

Chalmers infrastruktur