UC San Diego

We study the theory of pattern matching in Fn,k, the set of column strict fillings of k x n rectangular arrays with the integers 1, . . . , kn. We focus on finding the generating function for the number of consecutive occurrences in elements of Fn,k, of a pattern, T , where T is a standard tableau of shape jk. We show that the generating function for the number of consecutive occurrences of a standard tableau, T , of shape jk , where T has the minimal overlapping property, i.e. any two consecutive occurrences of T in an element, F in Fn,k, can overlap in exactly one column, can be expressed in terms of the number of maximum packings of T that are elements G in Fn (j - 1) + 1,k which have consecutive occurrences of T starting at positions 1, (j - 1) + 1, 2 (j - 1) + 1, . . . (n - 1) (j -1) + 1. When j = 2, our generating functions can be viewed as generalizations of the generating function for the number of rises in a permutation. When j > 2, our generating functions are generalizations of the generating functions for the number of consecutive occurrences of minimal overlapping permutations in permutations due to Duane and Remmel. We also find generalizations of André's results on the generating functions for the number of up-down permutations in terms of maximum packings. We develop several methods for computing the number of maximum packings, G in Fn (j -1) + 1,k, for T , for certain classes of standard tableaux, T , of shape jk. In particular, we completely classify the standard tableaux, T , of shape jk , that have the minimal overlapping property and are such that there is precisely one maximum packing, G in Fn (j -1) + 1,k, for T , for any n ̲>1