Penn Arts & Sciences Logo

Probability and Combinatorics

Thursday, February 19, 2004 - 4:30pm

Sergey Kitaev

University of Kentucky

Location

University of Pennsylvania

DRL 4N30

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.