Pattern avoidance in permutations: Linear and cyclic orders
type: Item
instance of: scholarly article
title: Pattern avoidance in permutations: Linear and cyclic orders
zbMATH Open document ID: 1035.05010
author: Antoine Vella
published in: The Electronic Journal of Combinatorics
publication date: 2004-02-05T00:00:00Z
full work available at URL: https://eudml.org/doc/123425
full work available at URL: v9i2r18.html
review text: The author extends the concept of pattern avoidance to cyclically ordered sets. This modification allows circular shifts in the values and/or the positions of a permutation. In both cases, the enumeration problem for all patterns of length up to 4 is dealt with. Using Krattenthaler's bijections between pattern-avoiding permutations and Dyck paths, the author shows the correspondence between two classes of pattern-avoiding cyclic arrangements and classes of Dyck paths (non-decreasing Dyck paths, first considered by Barcucci et al., and Dyck paths having at most one long vertical or horizontal edge). Both of these path classes can also be linked with examples of simultaneous pattern avoidance in the classical (linear) case. The study of some of their parameters yields results on the distribution of certain statistics on 321-avoiding permutations. In particular, the number of 321-avoiding permutations with precisely \(k\) descents is given.
reviewed by: Astrid Reifegerste
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 2038333
zbMATH Keywords: pattern avoidance
zbMATH Keywords: linear and cyclic orders
zbMATH Keywords: permutations
zbMATH Keywords: permutation statistics
zbMATH Keywords: Dyck paths
zbMATH Keywords: path statistics
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2038333