Department of Mathematics,
University of California San Diego
****************************
Special Combinatorics
Sergey Kataev
University of Kentucky
Non-overlapping patterns in permutations and words
Abstract:
A descent in a permutation a(1)a(2)...a(n) is an i such that a(i) > a(i+1). The distribution of the number of descents is given by the well known Eulerian numbers. We define a new statistic, namely the maximum number of non-overlapping descents in a permutation. Two descents i and j overlap if |i-j| = 1. We find the distribution of this new statistic using partially ordered generalized patterns (POGPs). The POGPs are generalizations of the Babson-Steingrimsson patterns, which in turn generalize the classical permutation patterns. A segment pattern is a pattern whose occurrence in a permutation is required to consist of consecutive letters of the permutation. As an example, the number of descents corresponds to the segment pattern 21. Let P be an arbitrary segment pattern. Using POGPs, we give the exponential generating function (e.g.f.) for the entire distribution of the maximum number of non-overlapping occurrences of P, provided we know the e.g.f. for the number of permutations that avoid P. We also discuss POGPs in words (with repeated letters), where we get results similar to those for permutations.
Host: Jeff Remmel
March 5, 2004
12:00 PM
AP&M 6218
****************************