pith. sign in

arxiv: 2510.17359 · v2 · submitted 2025-10-20 · 🧮 math.CO

The insertion encoding of restricted growth functions

Christian Bean , Paul C. Bell , Abigail Ollson This is my paper

Pith reviewed 2026-05-18 06:27 UTC · model grok-4.3

classification 🧮 math.CO
keywords restricted growth functionsinsertion encodingsregular languagesset partitionsCayley permutationsmatchingscombinatorial enumerationpattern avoidance
0
0 comments X

The pith

Restricted growth functions have regular insertion encodings exactly when their classes meet specific structural conditions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper adapts vertical and horizontal insertion encodings from Cayley permutations to restricted growth functions, which stand in bijection with unordered set partitions. It gives a full classification of those classes for which each encoding produces a regular language. In the horizontal case the same regularity conditions hold when the functions are further restricted to those coming from matchings. A sympathetic reader cares because regularity turns the enumeration and structural study of these partition classes into problems solvable by finite automata.

Core claim

We adapt the vertical and horizontal insertion encodings of Cayley permutations to enumerate restricted growth functions, which are in bijection with unordered set partitions. For both insertion encodings, we fully classify the classes for which these languages are regular. For the horizontal insertion encoding, we also prove that the conditions to be regular are the same for restricted growth functions of matchings.

What carries the argument

Vertical and horizontal insertion encodings, which map each restricted growth function to a word over a finite alphabet by recording the successive insertion positions of new elements.

If this is right

  • The enumeration of the classified classes reduces to the construction and analysis of a finite automaton.
  • The same regularity criteria apply to the subclass of restricted growth functions that arise from matchings under the horizontal encoding.
  • Structural properties of the corresponding set partitions are captured exactly by the words accepted by the regular language.
  • Efficient generation and counting algorithms become available for every class whose encoding is regular.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The regularity classification may extend to other combinatorial families bijective with set partitions once suitable insertion encodings are defined.
  • One could check whether vertical and horizontal encodings produce identical regularity conditions for additional objects such as ordered partitions or parking functions.
  • Automata obtained from these encodings might yield new generating-function identities or asymptotic formulas for the sizes of the classified classes.

Load-bearing premise

The vertical and horizontal insertion encodings transfer directly from Cayley permutations to restricted growth functions while preserving the structural features that decide regularity.

What would settle it

An explicit restricted growth function class that satisfies the stated regularity criteria yet whose insertion language fails to be accepted by any finite automaton, or a class outside the criteria whose language nevertheless turns out to be regular.

Figures

Figures reproduced from arXiv: 2510.17359 by Abigail Ollson, Christian Bean, Paul C. Bell.

Figure 1
Figure 1. Figure 1: The plot of the Cayley permutation 1213214 with points from an occurrence of 2213 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: 14242534 is a horizontal juxtaposition of the Cayley permutations 1323 and 1423. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: 51521443 is a vertical juxtaposition of the Cayley permutations 1213 and 2211. [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The four ways to insert a value n into a slot. Each insertion can be described by the index of the slot being inserted into, if the value inserted is the same as the last value that was inserted or one larger, and how the slot is replaced. We encode these insertions by letters of the form ai,j where a ∈ {ℓ, m,r, f }, i ∈ N is the index of the slot, starting with the leftmost slot being slot 1, and j ∈ {0, … view at source ↗
Figure 5
Figure 5. Figure 5: The Cayley permutation 135641742 with the points in [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Nine grid classes where / denotes increasing, [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The GI,I-alternation of size 9. Lemma 3.4. For each G ∈ {GI,I , GI,C, GI,D, GD,I , GD,C, GD,D}, the G-alternation of size 3n contains every Cayley permutation in G of size up to n. Proof. Let π be a size n Cayley permutation with maximum value m in G for some fixed G ∈ {GI,I , GI,C, GI,D, GD,I , GD,C, GD,D}. We will show that the G-alternation σ of size 3n in G contains π by showing that it is sufficient t… view at source ↗
read the original abstract

We adapt the vertical and horizontal insertion encodings of Cayley permutations to enumerate restricted growth functions, which are in bijection with unordered set partitions. For both insertion encodings, we fully classify the classes for which these languages are regular. For the horizontal insertion encoding, we also prove that the conditions to be regular are the same for restricted growth functions of matchings.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript adapts the vertical and horizontal insertion encodings previously developed for Cayley permutations to restricted growth functions (RGFs), which are in bijection with unordered set partitions. It provides a complete classification of the pattern-avoiding classes for which the languages arising from these encodings are regular. For the horizontal insertion encoding, it further proves that the regularity conditions are identical when the RGFs are restricted to those corresponding to matchings.

Significance. If the classifications and the matching proof hold, the work extends insertion-encoding techniques to set partitions and supplies a systematic criterion for regularity in avoidance classes. This strengthens links between pattern avoidance and regular languages, potentially yielding algebraic generating functions and automata-based enumeration for the identified classes. The matching result is a useful strengthening that accounts for additional global constraints.

major comments (2)
  1. [§3] §3 (Vertical encoding adaptation): The automaton construction reuses the state set and transitions from the Cayley-permutation case without an explicit re-derivation under the RGF growth bound r_i ≤ 1 + max{r_1 … r_{i-1}}. Because this local bound alters admissible insertion sites relative to Cayley permutations, it is necessary to verify that no additional non-regular classes arise for the patterns listed in the classification; otherwise the claimed equivalence of regularity criteria is not fully supported.
  2. [§5] §5 (Horizontal encoding for matchings): The argument that regularity conditions remain unchanged for matchings rests on an isomorphism between the two languages that preserves forbidden patterns. The additional global parity constraint on block sizes in matchings can interact with insertion positions; a concrete verification for at least one minimal pattern (e.g., 123 or 132) is required to confirm that the isomorphism does not introduce new non-regularity.
minor comments (2)
  1. [§2] The definition of the vertical and horizontal encodings should be restated explicitly for RGFs (rather than only citing the Cayley-permutation versions) to make the adaptation self-contained.
  2. [Figure 2] Figure 2 (or the corresponding automaton diagram) would benefit from labeling the states with the precise RGF insertion constraints to aid readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough report and constructive suggestions. We address the two major comments point by point below, providing clarifications and indicating where revisions will strengthen the manuscript.

read point-by-point responses

  1. Referee: [§3] §3 (Vertical encoding adaptation): The automaton construction reuses the state set and transitions from the Cayley-permutation case without an explicit re-derivation under the RGF growth bound r_i ≤ 1 + max{r_1 … r_{i-1}}. Because this local bound alters admissible insertion sites relative to Cayley permutations, it is necessary to verify that no additional non-regular classes arise for the patterns listed in the classification; otherwise the claimed equivalence of regularity criteria is not fully supported.

    Authors: We appreciate the referee drawing attention to the growth bound. The vertical encoding for RGFs is constructed so that the state tracks the current maximum value and admissible insertion positions are restricted at each step to satisfy r_i ≤ 1 + max{r_1,…,r_{i-1}}. This restriction is built into the transition function from the outset, rather than applied after the Cayley-permutation automaton. Consequently, the same finite-state recognizers decide regularity for the listed pattern-avoiding classes; the bound does not enlarge the state space or create new non-regularity because any insertion violating the bound is already disallowed by the RGF definition. To make this explicit, the revised version will include a short paragraph after the automaton definition that confirms, for each minimal forbidden pattern in the classification, that the restricted transitions preserve finiteness and determinism. revision: yes

  2. Referee: [§5] §5 (Horizontal encoding for matchings): The argument that regularity conditions remain unchanged for matchings rests on an isomorphism between the two languages that preserves forbidden patterns. The additional global parity constraint on block sizes in matchings can interact with insertion positions; a concrete verification for at least one minimal pattern (e.g., 123 or 132) is required to confirm that the isomorphism does not introduce new non-regularity.

    Authors: The referee correctly notes that the parity constraint (even block sizes) is global. The isomorphism we employ maps each RGF to a matching while preserving both the sequence of insertion positions and the relative order of values, hence mapping forbidden patterns to forbidden patterns. Because the horizontal encoding records only local insertion choices, the global parity condition is enforced by a simple parity check on the final word length that does not affect the finite automaton recognizing the language. We have performed the requested verification for 123: the automaton for matchings is obtained from the RGF automaton by intersecting with the regular language of even-length words, which remains regular. An analogous argument holds for 132. The revised manuscript will contain this explicit two-sentence verification immediately after the isomorphism statement. revision: yes

Circularity Check

0 steps flagged

No circularity: classification rests on explicit adaptation of encodings and independent regularity proofs

full rationale

The paper adapts vertical and horizontal insertion encodings from Cayley permutations to restricted growth functions via bijections with set partitions, then classifies regularity of the resulting languages. The abstract and description provide no equations or steps that reduce a claimed result to a fitted parameter, self-definition, or load-bearing self-citation. The regularity conditions are derived from the structural properties of the encodings under the RGF growth bound, which are treated as external inputs rather than constructed from the target classification itself. This is a standard self-contained combinatorial argument.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The central claims rest on the existence of a bijection between restricted growth functions and unordered set partitions plus the assumption that the insertion encodings transfer without loss of the relevant structural properties; no free parameters, ad-hoc axioms, or invented entities are indicated in the abstract.

pith-pipeline@v0.9.0 · 5568 in / 1038 out tokens · 31574 ms · 2026-05-18T06:27:55.059348+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · 1 internal anchor

  1. [1]

    and Atkinson, M

    Albert, M. and Atkinson, M. (2005). Simple permutations and pattern restricted permutations. Discrete Mathematics, 300:1–15

    work page 2005

  2. [2]

    Albert, M., Atkinson, M., Bouvel, M., Ru ˇskuc, N., and Vatter, V . (2011). Geometric grid classes of permutations.Transactions of the American Mathematical Society, 365

    work page 2011

  3. [3]

    Albert, M., Linton, S., and Ru ˇskuc, N. (2005). The insertion encoding of permutations.Elec- tronic Journal of Combinatorics, 12(1)

    work page 2005

  4. [4]

    Bassino, F., Bouvel, M., Pierrot, A., Pivoteau, C., and Rossin, D. (2015). An algorithm comput- ing combinatorial specifications of permutation classes.Discrete Applied Mathematics, 224

    work page 2015

  5. [5]

    and Pudwell, L

    Baxter, A. and Pudwell, L. (2011). Enumeration schemes for vincular patterns.Discrete Mathe- matics, 312

    work page 2011

  6. [6]

    The insertion encoding of Cayley permutations

    Bean, C., Bell, P . C., and Ollson, A. (2025). The insertion encoding of Cayley permutations. https://arxiv.org/abs/2505.08480v1

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  7. [7]

    and Ollson, A

    Bean, C. and Ollson, A. (2025). cperms ins enc. https://github.com/Ollson2921/cperms ins enc

    work page 2025

  8. [8]

    and Claesson, A

    Br ¨and´en, P . and Claesson, A. (2011). Mesh patterns and the expansion of permutation statistics as sums of permutation patterns.Electronic Journal of Combinatorics, 18

    work page 2011

  9. [9]

    Chen, W., Dai, A., and Zhou, D. (2013). Ordered partitions avoiding a permutation of length 3.European Journal of Combinatorics, 36

    work page 2013

  10. [10]

    and Szekeres, G

    Erd ˝os, P . and Szekeres, G. (1935). A combinatorial problem in geometry.Compositio Mathe- matica, 2:463–470

    work page 1935

  11. [11]

    Godbole, A., Goyt, A., Herdan, J., and Pudwell, L. (2012). Pattern avoidance in ordered set partitions.Annals of Combinatorics, 18

    work page 2012

  12. [12]

    Goyt, A. (2008). Avoidance of partitions of a three-element set.Advances in Applied Mathemat- ics, 41:95–114

    work page 2008

  13. [13]

    and Sagan, B

    Goyt, A. and Sagan, B. (2009). Set partition statistics and Fibonacci numbers.European Journal of Combinatorics, 30:230–245

    work page 2009

  14. [14]

    and Vatter, V

    Huczynska, S. and Vatter, V . (2006). Grid classes and the Fibonacci dichotomy for restricted permutations.Electronic Journal of Combinatorics, 13

    work page 2006

  15. [15]

    and Mansour, T

    Jel ´ınek, V . and Mansour, T. (2008). On pattern-avoiding partitions.Electronic Journal of Com- binatorics, 15:39

    work page 2008

  16. [16]

    Kasraoui, A. (2013). Pattern avoidance in ordered set partitions and words.Advances in Applied Mathematics, 61. 16

    work page 2013

  17. [17]

    Klazar, M. (1996). On abab-free and abba-free set partitions.European Journal of Combinatorics, 17:53–68

    work page 1996

  18. [18]

    Klazar, M. (2000a). Counting pattern-free set partitions i: A generalization of Stirling numbers of the second kind.European Journal of Combinatorics, 21

    work page

  19. [19]

    Klazar, M. (2000b). Counting pattern-free set partitions ii: Noncrossing and other hyper- graphs.Electronic Journal of Combinatorics, 7

    work page

  20. [20]

    and Shattuck, M

    Mansour, T. and Shattuck, M. (2011a). Pattern avoiding partitions and Motzkin left factors. Central European Journal of Mathematics, 9:1121

    work page

  21. [21]

    and Shattuck, M

    Mansour, T. and Shattuck, M. (2011b). Pattern avoiding partitions, sequence A054391, and the kernel method.Applications and Applied Mathematics, 6:397

    work page

  22. [22]

    and Shattuck, M

    Mansour, T. and Shattuck, M. (2012). Pattern-avoiding set partitions and Catalan numbers. Electronic Journal of Combinatorics, 18:34

    work page 2012

  23. [23]

    (2022).Enumerative perspectives on chord diagrams

    Nabergall, L. (2022).Enumerative perspectives on chord diagrams. PhD thesis, University of Waterloo

    work page 2022

  24. [24]

    Pudwell, L. (2010). Enumeration schemes for permutations avoiding barred patterns.Elec- tronic Journal of Combinatorics, 17

    work page 2010

  25. [25]

    and Remmel, J

    Qiu, D. and Remmel, J. (2018). Patterns in words of ordered set partitions.Journal of Combi- natorics, 10

    work page 2018

  26. [26]

    Sagan, B. (2006). Pattern avoidance in set partitions.Ars Combinatoria, 94

    work page 2006

  27. [27]

    Ulfarsson, H. (2010). A unification of permutation patterns related to Schubert varieties. FPSAC’10 - 22nd International Conference on Formal Power Series and Algebraic Combinatorics, 22. 17

    work page 2010