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: