The University of Michigan Combinatorics Seminar
Fall 2000
October 20, 4:10-5:00, 3866 East Hall





Pattern Frequency Sequences and Internal Zeros

Bruce Sagan

Michigan State University




Abstract

Let q=q1 q2... qk be a permutation in the symmetric group Sk. We say that the permutation p=p1 p2...pn in Sn contains a q-pattern if there is a set of indices iq1< iq2 < ... < iqk such that the elements of the subsequence pi1pi2... pik are in the same relative order as those in q. For example, 41523 contains exactly two 132-patterns, namely 152 and 153. We let

Sn,q(c) = the number of n-permutations with exactly c patterns of type q.

The numbers Sn,q(0) have been extensively studied for different patterns q and we propose looking at the sequence (Sn,q(c)). When q=21 this sequence counts inversions and is well-known to be unimodal (first increasing and then decreasing). We show that this is not true in general, for any pattern in S3. In fact there are an infinite number of values of n for which the sequence has internal zeros (a string of zeros with nonzero terms on either side).

This is joint work with Miklós Bóna and Vincent Vatter.