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.
Probability and Combinatorics
Thursday, February 19, 2004 - 4:30pm
Sergey Kitaev
University of Kentucky