What is the idea?

Start with a sequence of nonnegative integers. Reusing a value that has appeared before increases the allowance for future values. The rule remembers repetition, not just the current maximum.

That makes the model look local and self-contained. The surprise comes from counting the possible next moves: old values and new values split in exactly the same way as legal insertion positions in the standard generating tree for simsun permutations.

1

Reuse

Choose a value that already appeared.

2

Growth

Each reuse raises the future admissible bound.

3

Same tree

The old/new extension counts match simsun insertion counts exactly.

Why is it interesting?

The rule is not introduced merely to manufacture another sequence family. Its growth mechanism has an exact structural counterpart in a classical permutation class. That gives a direct recursive bijection, not just matching counting sequences.

Pattern avoidance then shows that the analogy has limits. Some restrictions collapse to simple formulas; others lead to algebraic generating functions, factorial lower bounds, or ordered state systems. The model therefore sits close enough to inversion sequences and level sequences to compare, but far enough away to produce genuinely different avoidance behavior.

Main results

01

Simsun bijection

A direct recursive bijection maps reuse-growth sequences to simsun permutations, with descents tracking distinct values and ascents tracking repetitions.

02

A second bijection and Euler numbers

There is also a recursive bijection with 000-avoiding inversion sequences. In particular, |Uₙ| = Eₙ₊₁, where E_j are the Euler zigzag numbers.

03

All 13 length-three packed patterns

The paper gives a structural treatment of every packed pattern of length 3; six single-pattern avoidance classes receive closed enumerations.

04

The 102 class

Its ordinary generating function is algebraic. The same class coincides with 102-avoiding level sequences, so the result enumerates those as well.

05

Beyond exponential growth

The 010, 100, 101 and 110 classes have factorial lower bounds and are superexponential. For {201,210}, a three-parameter state reduction yields an explicit algebraic generating function and asymptotics; the inversion-sequence Wilf equivalences 101~110 and 201~210 do not survive here.

For specialists

Abstract

We introduce reuse-growth sequences, a class of statistic-controlled restricted-growth words in which the admissible range increases whenever a previously seen value is reused. The class is singled out by a simple insertion property. If a prefix has length m and contains d distinct values, then it has exactly d extensions by old values and m + 2 − 2d extensions by new values. These are precisely the two insertion counts in the standard generating tree for simsun permutations. Matching the two types of extensions gives a direct recursive bijection between reuse-growth sequences and simsun permutations, with des = d − 1, asc = rep. A second recursive bijection maps reuse-growth sequences to 000-avoiding inversion sequences. Consequently, |Uₙ| = Eₙ₊₁, with the bijections providing statistic refinements rather than only an equinumeracy. We then develop the length-three pattern-avoidance theory of the class. All thirteen packed patterns are treated structurally. Six single-pattern classes have closed enumerations. For 102, the ordinary generating function satisfies A = 1 + x(1 − x)A² + x²(1 − x)A³, from which we obtain a coefficient formula and square-root asymptotics. Moreover, U_n(102) coincides with the corresponding class of level sequences, so this result also enumerates 102-avoiding level sequences. Four further single-pattern classes admit exact succession rules and are superexponential, while 120, 201, and 210 require ordered used/unused states. For the pair {201, 210}, these states reduce to three parameters, leading to an explicit algebraic generating function and asymptotics. The resulting avoidance theory differs substantially from that of inversion sequences; in particular, the inversion-sequence Wilf equivalences 101 ~ 110 and 201 ~ 210 do not persist for reuse-growth sequences.

Key formulas

Definitionw₁ = 0,   wᵢ ≤ 1 + rep(w₁…wᵢ₋₁)
Euler enumeration|Uₙ| = Eₙ₊₁
102 avoidanceA₁₀₂ = 1 + x(1−x)A₁₀₂² + x²(1−x)A₁₀₂³

Citation / BibTeX

@misc{kleiner2026reusegrowth,
  author = {Igor Kleiner},
  title = {Reuse-Growth Sequences: Insertion Bijections and Pattern Avoidance},
  year = {2026},
  month = sep,
  note = {Preprint},
  doi = {10.5281/zenodo.22915110},
  url = {https://doi.org/10.5281/zenodo.22915110}
}