Return-Growth Sequences: Euler Enumeration and Pattern Avoidance

Abstract

A return-growth sequence is a restricted-growth word whose admissible range expands only when the word returns to a previously used value after leaving it; an adjacent repetition does not enlarge the range. Compressing maximal constant runs separates a word into a run skeleton carrying all return information and a composition recording run lengths. We construct explicit recursive bijections from run skeletons to 000-avoiding inversion sequences and directly to simsun permutations, yielding an Euler-number enumeration and statistic refinements. We also study classical pattern avoidance. Eight of the thirteen length-three patterns have closed enumerations; 021-avoiding skeletons are Motzkin-enumerated, while restoring run lengths gives partial sums of Catalan numbers. For the pair {201,210}, an infinite binary frontier is reduced by a first-hit decomposition to a quadratic kernel, yielding an algebraic generating function.