Printable PDF
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

****************************