#####
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: