Pattern Frequency Sequences and Internal Zeros

Let q=q₁ q₂... q_k be a permutation in the symmetric group S_k. We say that the permutation p=p₁ p₂...p_n in S_n contains a q-pattern if there is a set of indices i_q1< i_q2 < ... < i_qk such that the elements of the subsequence p_i1p_i2... p_ik are in the same relative order as those in q. For example, 41523 contains exactly two 132-patterns, namely 152 and 153. We let

The numbers S_n,q(0) have been extensively studied for different patterns q and we propose looking at the sequence (S_n,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 S₃. 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.