Séminaire Lotharingien de Combinatoire, B48e (2003), 19 pp.
Generalized Pattern Avoidance with Additional
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
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: