Séminaire Lotharingien de Combinatoire, B48e (2003), 19 pp.
Sergey Kitaev
Generalized Pattern Avoidance with Additional
Restrictions
Abstract.
Babson and Steingrímsson introduced generalized permutation
patterns that allow the requirement that two adjacent letters in a
pattern must be adjacent in the permutation. We consider
n-permutations that avoid the generalized pattern 1-32 and whose
k
rightmost letters form an increasing subword. The number of such
permutations is a linear combination of Bell numbers. We find a
bijection between these permutations and all partitions of an
(n-1)-element set with one subset marked that satisfy certain
additional conditions. Also we find the e.g.f. for the number of
permutations that avoid a generalized 3-pattern with no dashes and whose
k leftmost or k rightmost letters form either an increasing or
decreasing subword. Moreover, we find a bijection between
n-permutations that avoid the pattern 132 and begin with the
pattern 12 and increasing rooted trimmed trees with n+1 nodes.
Received: May 15, 2002.
Accepted: January 2, 2003.
The following versions are available: