Stable Consecutive Patterns and Chain Clusters
Overview
A consecutive permutation pattern specifies the relative order of a block of distinct adjacent letters. We classify the patterns whose occurrence distribution is unchanged when the numbers of copies assigned to the letters are permuted. The criterion is that each connected group of overlapping occurrences forces one total order on its positions. We give a sharp finite pair-count test, nonmonotone stable examples such as 12435, exact-position refinements and a joint criterion for same-length patterns beginning with their smallest letter.
Original abstract (English)
A consecutive permutation pattern is stable if its occurrence distribution on words is unchanged when the multiplicities of the letters are permuted. We prove that the stable patterns are precisely the chain patterns of Elizalde and Noy: every connected system of overlapping occurrences must impose a total order on its positions. For a pattern of length m, it suffices to count pairs of occurrences in words on multisets of size at most 2m-1 with one doubled letter and all other letters single. For m ≥ 3, this length bound is sharp. A finite two-occurrence overlap criterion gives an equivalent structural test. Stable patterns also have invariant occurrence-position distributions; their marked-position enumerators are nonnegative combinations of products of elementary symmetric functions. The characterization supplies nonmonotone stable patterns of every length at least five, disproving a conjecture of Chen, Fang and Kitaev. We give weighted generating functions and the classification through length five. Corresponding criteria treat joint distributions for families beginning with their smallest letter. Two individually stable patterns of length five furnish an explicit failure of joint stability.
Mathematical review
The manuscript has completed internal review. Complete formalization is not yet established for this public version.
Review standard