pith. sign in

arxiv: 2505.08480 · v2 · submitted 2025-05-13 · 🧮 math.CO

The insertion encoding of Cayley permutations

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

Pith reviewed 2026-05-22 15:38 UTC · model grok-4.3

classification 🧮 math.CO
keywords Cayley permutationsinsertion encodingregular languagesgenerating functionspop-stack sortingenumerative combinatoricsformal languages
0
0 comments X

The pith

Vertical and horizontal insertion encodings fully classify the Cayley permutation classes whose languages are regular.

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

The paper introduces vertical and horizontal insertion encodings for Cayley permutations as natural generalizations of the insertion encoding for ordinary permutations. It classifies exactly which Cayley permutation classes produce regular languages under these encodings. For those classes the authors supply an algorithm that computes the corresponding rational generating functions. The method is applied to enumerate the hare pop-stack sortable Cayley permutations and thereby resolves an open problem posed by Cerbai.

Core claim

The vertical and horizontal insertion encodings turn Cayley permutation classes into formal languages, and the authors prove a complete classification of the classes for which these languages are regular. This classification comes with an algorithm to calculate the rational generating function for any such class. Using the algorithm, the number of hare pop-stack sortable Cayley permutations is determined, answering a question left open by Cerbai.

What carries the argument

The vertical and horizontal insertion encodings, which extend the classical insertion encoding by recording positions in a two-dimensional grid adapted to the structure of Cayley permutations.

If this is right

  • The regularity of the encoding languages is completely determined for all Cayley permutation classes.
  • Rational generating functions for the enumerated classes can be computed by a uniform algorithm.
  • The enumeration of hare pop-stack sortable Cayley permutations is obtained explicitly.

Where Pith is reading between the lines

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

  • These encodings may help classify regularity for insertion-based encodings in other combinatorial families that allow repeated entries.
  • The solved enumeration opens the way for asymptotic analysis of the growth rates of these sortable objects.

Load-bearing premise

These encodings are assumed to extend the classical method while keeping the structural features required to classify regularity in every possible case.

What would settle it

A Cayley permutation class whose insertion encoding language is shown to be non-regular by direct construction while the classification claims it is regular, or a mismatch in the computed count of hare pop-stack sortable objects against an independent enumeration method.

Figures

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

Figure 1
Figure 1. Figure 1: The plot of the Cayley permutation 21321. [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The evolution of the Cayley permutation 31232. [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The four ways to insert a number n into a slot. 4 [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The evolution of a Cayley permutation 31232 with the encoding shown with each inser [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Examples of vertical juxtapositions. A Cayley permutation can be in more than one of these nine classes, such as 23145. The sequence 2345 is strictly increasing, and the sequence 1 is strictly increasing, strictly decreasing, and con￾stant, hence 23145 is in VI,I , VD,I and VC,I . This is always the case when the values can be split so that there is a single 1 on its own, hence the Cayley permutations 12 a… view at source ↗
Figure 6
Figure 6. Figure 6: The Cayley permutation 35125224 on a grid with positions [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: An occurrence of the gridded Cayley permutation [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The tiling representing the set of derivations from the configuration [PITH_FULL_IMAGE:figures/full_fig_p013_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The intermediate tiling representing the configuration 2 [PITH_FULL_IMAGE:figures/full_fig_p014_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Intermediate tiling representing the configuration 2 [PITH_FULL_IMAGE:figures/full_fig_p015_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Adding basis elements from the class Av(123) to an intermediate tiling as obstructions and simplifying. By the second simplification, any obstructions with an index in a point cell can be simplified to a smaller obstruction. This is done in Figure 11b. And finally, the obstructions can be simplified again by containment, as in Figure 11c. More details of simplifying tilings are given in Section 6.3.2 of A… view at source ↗
Figure 12
Figure 12. Figure 12: The tiling representing the the configuration [PITH_FULL_IMAGE:figures/full_fig_p016_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: The four intermediate tilings representing configurations after one insertion into [PITH_FULL_IMAGE:figures/full_fig_p016_13.png] view at source ↗
Figure 15
Figure 15. Figure 15: The configuration B represents, 1 ⋄ , has eight possible insertions; f1,0, ℓ1,0, r1,0, m1,0, f1,1, ℓ1,1, r1,1, and m1,1. The children of B are shown in the same respective order. 16 [PITH_FULL_IMAGE:figures/full_fig_p016_15.png] view at source ↗
Figure 14
Figure 14. Figure 14: A rule showing the parent tiling representing [PITH_FULL_IMAGE:figures/full_fig_p017_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Another rule for the class Av(123). As we keep track of occurrences of basis patterns through obstructions, the point cells do not add any information so we can remove them from our tilings. This is called factoring in Albert et al. [3]. We can apply the same factoring conditions that they use to our tilings, except that we can additionally factor cells in point rows. Every point cell and the column it is… view at source ↗
Figure 16
Figure 16. Figure 16: Examples of factorising tilings. which recognises the vertical insertion encodings of the slot-bounded Cayley permutation class of interest. In the next section we give a full example of a DFA constructed using this method for the class Av(231, 312, 2121). 4.2 Implementation of the algorithm We have implemented the algorithm described in Section 4.1 in Python. For the horizontal in￾sertion encoding, which… view at source ↗
Figure 17
Figure 17. Figure 17: S → f1,1 | ℓ1,1A | r1,1B | m1,1C ∗ A → ∗ f1,1 + ∗ ℓ1,1 + ∗ r1,1 + ∗ m1,1 + ∗ f1,0 + ∗ ℓ1,0 + ∗ r1,0 + ∗ m1,0 ∗ A → ∗ P + ∗ P × ∗ A + ∗ P × B + ∗ P × ∗ C + ∗ P + ∗ P × ∗ A + ∗ P × B + ∗ P × ∗ C [PITH_FULL_IMAGE:figures/full_fig_p019_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: A → f1,1 | ℓ1,1A | r1,1B | m1,1C | f1,0 | ℓ1,0A | r1,0B | m1,0C 19 [PITH_FULL_IMAGE:figures/full_fig_p019_18.png] view at source ↗
Figure 19
Figure 19. Figure 19: B → f1,1 | ℓ1,1D | r1,1B | m1,1E ∗ C → ∗ f2,0 + ∗ ℓ2,0 + ∗ f1,1 + ∗ ℓ1,1 + ∗ r1,1 + ∗ m1,1 ∗ C → ∗ P × B + ∗ P × ∗ C + ∗ P × A + ∗ P × ∗ F + ∗ P × G + ∗ P × H [PITH_FULL_IMAGE:figures/full_fig_p020_19.png] view at source ↗
Figure 20
Figure 20. Figure 20: C → f2,0B | ℓ2,0C | f1,1A | ℓ1,1F | r1,1G | m1,1H 20 [PITH_FULL_IMAGE:figures/full_fig_p020_20.png] view at source ↗
Figure 21
Figure 21. Figure 21: D → f1,0 | ℓ1,0D ∗ E → ∗ f2,0 + ∗ ℓ2,0 ∗ E → ∗ P × B + ∗ P × ∗ E [PITH_FULL_IMAGE:figures/full_fig_p021_21.png] view at source ↗
Figure 22
Figure 22. Figure 22: E → f2,0B | ℓ2,0E ∗ F → ∗ f1,0 + ∗ ℓ1,0 ∗ F → ∗ P × A + ∗ P × ∗ F [PITH_FULL_IMAGE:figures/full_fig_p021_22.png] view at source ↗
Figure 23
Figure 23. Figure 23: H → f1,0A | ℓ1,0H 21 [PITH_FULL_IMAGE:figures/full_fig_p021_23.png] view at source ↗
Figure 24
Figure 24. Figure 24: G → f1,1A | ℓ1,1F | r1,1G | m1,1H H → ∗ f2,0 + ∗ ℓ1,0 H → ∗ P × G + ∗ P × H [PITH_FULL_IMAGE:figures/full_fig_p022_24.png] view at source ↗
Figure 25
Figure 25. Figure 25: H → f2,0F | ℓ1,0F 22 [PITH_FULL_IMAGE:figures/full_fig_p022_25.png] view at source ↗
Figure 26
Figure 26. Figure 26: The horizontal evolution of the Cayley permutation 243441. [PITH_FULL_IMAGE:figures/full_fig_p024_26.png] view at source ↗
Figure 27
Figure 27. Figure 27: The horizontal evolution of the Cayley permutation 243441 with the encoding shown [PITH_FULL_IMAGE:figures/full_fig_p025_27.png] view at source ↗
Figure 28
Figure 28. Figure 28: Slots imply the existence of values in the prefix of a configuration. [PITH_FULL_IMAGE:figures/full_fig_p025_28.png] view at source ↗
Figure 29
Figure 29. Figure 29: Configurations which do not satisfy the conditions of Proposition 5.2 have smaller [PITH_FULL_IMAGE:figures/full_fig_p027_29.png] view at source ↗
Figure 30
Figure 30. Figure 30: The horizontal juxtapositions 13124 ∈ HI,I and 421234 ∈ HD,I . a horizontal alternation. By symmetry Lemma 3.2 can be immediately adapted to Lemma 5.4 for horizontal alternations. Lemma 5.4. For each H ∈ {HI,I , HI,D, HD,I , HD,D}, the size 2n horizontal alternation in H con￾tains every horizontal juxtaposition in H of size up to n. We are ready to prove the main theorem of this section, Theorem 5.5. Theo… view at source ↗
read the original abstract

We introduce the vertical and horizontal insertion encodings for Cayley permutations which naturally generalise the insertion encoding for permutations. In both cases, we fully classify the Cayley permutation classes for which these languages are regular, and provide an algorithm for computing the rational generating functions. We use our algorithm to solve an open problem of Cerbai by enumerating the hare pop-stack sortable Cayley permutations.

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 / 3 minor

Summary. The paper introduces vertical and horizontal insertion encodings for Cayley permutations that generalize the classical insertion encoding for permutations. It fully classifies the Cayley permutation classes for which these encodings yield regular languages, supplies an algorithm that computes the corresponding rational generating functions, and applies the algorithm to enumerate the hare pop-stack sortable Cayley permutations, thereby resolving an open problem of Cerbai.

Significance. If the classification and algorithm are correct, the work provides a systematic extension of insertion encodings to Cayley permutations and a concrete tool for producing rational generating functions in this setting. The resolution of Cerbai's enumeration problem demonstrates the method's utility for open questions in pattern avoidance and sortable structures.

major comments (2)
  1. §4 (algorithm description): the correctness argument for the procedure that converts a regular language into a rational generating function should explicitly address how the finite-state automaton is constructed from the insertion rules for Cayley permutations; without this, it is unclear whether the algorithm remains valid when the underlying class is not a classical permutation class.
  2. Theorem 5.2 (classification of regular cases): the case analysis establishing that only the listed families produce regular languages must include an explicit argument that every possible Cayley permutation class falls into one of the enumerated cases; the current outline leaves open the possibility that an unlisted class could still yield a regular language through an unforeseen interaction with the vertical or horizontal encoding.
minor comments (3)
  1. Introduction, paragraph 3: the definition of a Cayley permutation is given only by reference; a self-contained one-line characterization would help readers who are not already familiar with the object.
  2. Figure 2: the diagram illustrating a vertical insertion step would be clearer if the active sites were labeled with the same notation used in the surrounding text.
  3. §6 (application to hare pop-stack sortable permutations): the generating function obtained by the algorithm is stated without an accompanying closed-form expression or OEIS reference; adding either would facilitate independent verification.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and the constructive comments. The recommendation for minor revision is appreciated, and we address each major comment below. We will revise the manuscript to incorporate additional clarifications as outlined.

read point-by-point responses

  1. Referee: §4 (algorithm description): the correctness argument for the procedure that converts a regular language into a rational generating function should explicitly address how the finite-state automaton is constructed from the insertion rules for Cayley permutations; without this, it is unclear whether the algorithm remains valid when the underlying class is not a classical permutation class.

    Authors: We agree that the description in §4 would benefit from greater explicitness regarding the automaton construction. In the revised manuscript we will add a paragraph detailing how the states and transitions of the finite-state automaton are determined directly from the vertical and horizontal insertion rules specific to Cayley permutations (including the handling of repeated values). This will make clear that the correctness of the conversion to a rational generating function holds for general Cayley permutation classes and does not rely on the class being a classical permutation class. revision: yes

  2. Referee: Theorem 5.2 (classification of regular cases): the case analysis establishing that only the listed families produce regular languages must include an explicit argument that every possible Cayley permutation class falls into one of the enumerated cases; the current outline leaves open the possibility that an unlisted class could still yield a regular language through an unforeseen interaction with the vertical or horizontal encoding.

    Authors: The proof of Theorem 5.2 proceeds via an exhaustive case analysis on the possible forms of the insertion encodings and the avoidance conditions that preserve regularity. To address the referee's concern, we will insert an additional paragraph immediately after the case analysis that explicitly argues for completeness: any Cayley permutation class not belonging to one of the listed families must admit an encoding containing a substructure (such as an unbounded number of independent insertions) that produces a non-regular language, as shown by a pumping-lemma violation. This addition will eliminate any ambiguity about unlisted classes without changing the stated classification. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper introduces new vertical and horizontal insertion encodings as generalizations of the classical insertion encoding for permutations. It then classifies Cayley permutation classes for which the resulting languages are regular and supplies an algorithm to compute the associated rational generating functions. This algorithm is applied to resolve an external open enumeration problem posed by Cerbai. No quoted derivation step reduces a claimed prediction or classification result to a fitted parameter, a self-defined quantity, or a load-bearing self-citation whose validity is presupposed by the present work. The central claims rest on explicit case analysis and algorithmic construction rather than on renaming or circular re-use of prior outputs by the same authors.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; no explicit free parameters, invented entities, or non-standard axioms are identifiable from the given text. The work relies on standard definitions from formal language theory and permutation pattern literature.

axioms (1)
  • standard math Standard properties of regular languages and finite automata suffice to decide regularity and compute generating functions.
    Invoked implicitly when classifying languages as regular and when converting them to rational generating functions.

pith-pipeline@v0.9.0 · 5573 in / 1315 out tokens · 49152 ms · 2026-05-22T15:38:16.179364+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. The insertion encoding of restricted growth functions

    math.CO 2025-10 unverdicted novelty 6.0

    Classifies regularity of vertical and horizontal insertion encodings for restricted growth functions and extends the horizontal result to matchings.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · cited by 1 Pith paper

  1. [1]

    Ahlbach, C., Usatine, J., and Pippenger, N. (2012). Barred preferential arrangements.Electronic Journal of Combinatorics, 20

    work page 2012

  2. [2]

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

    work page 2005

  3. [3]

    H., Bean, C., Claesson, A., Nadeau, E., Pantone, J., and Ulfarsson, H

    Albert, M. H., Bean, C., Claesson, A., Nadeau, E., Pantone, J., and Ulfarsson, H. (2025). Com- binatorial exploration: An algorithmic framework for enumeration.Memoirs of the American Mathematical Society, to appear

    work page 2025

  4. [4]

    Atkinson, M. (1999). Restricted permutations.Discrete Mathematics, 195:27–38

    work page 1999

  5. [5]

    and Ollson, A

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

    work page 2025

  6. [6]

    Biers-Ariel, Y., Zhang, Y., and Godbole, A. (2016). Some results on superpatterns for preferen- tial arrangements.Advances in Applied Mathematics, 81

    work page 2016

  7. [7]

    Cayley, A. (1857). On the theory of analytic forms called trees.Philos. Mag. 13, 19-30, 1857. Reprinted in Mathematical Papers, 3:242–246

    work page

  8. [8]

    Cerbai, G. (2021). Sorting Cayley permutations with pattern-avoiding machines.Australasian Journal of Combinatorics, 80(3):322–341

    work page 2021

  9. [9]

    Chung, F., Graham, R., Hoggatt, V ., and Kleiman, M. (1978). The number of baxter permuta- tions.Journal of Combinatorial Theory, Series A, 24(3):382–394

    work page 1978

  10. [10]

    Claesson, A., Cerbai, G., Ernst, D., and Golab, H. (2024). Pattern-avoiding Cayley permuta- tions via combinatorial species. https://arxiv.org/abs/2407.19583. 30

    work page arXiv 2024

  11. [11]

    and Kravitz, N

    Defant, C. and Kravitz, N. (2020). Stack-sorting for words.Australasian Journal of Combina- torics, 77(1):51–68

    work page 2020

  12. [12]

    and Szekeres, G

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

    work page 1935

  13. [13]

    Foissy, L., Novelli, J., and Thibon, J.-Y. (2010). Polynomial realizations of some combinatorial Hopf algebras.Journal of Noncommutative Geometry, 8

    work page 2010

  14. [14]

    Golab, H. (2024). Pattern avoidance in Cayley permutations. Master’s thesis, Northern Ari- zona University

    work page 2024

  15. [15]

    Hazewinkel, M. (2004). Hopf algebras of endomorphisms of Hopf algebras.Arabian Journal for Science and Engineering, 33

    work page 2004

  16. [16]

    and Mansour, T

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

    work page 2008

  17. [17]

    Knuth, D. E. (1968).The Art of Computer Programming, volume 1. Addison-Wesley

    work page 1968

  18. [18]

    and Rhoades, B

    Kroes, D. and Rhoades, B. (2022). Packed words and quotient rings.Discrete Mathematics, 345:112945

    work page 2022

  19. [19]

    MacMahon, P . A. (1915).Combinatory analysis, volume 1. Cambridge University Press

    work page 1915

  20. [20]

    and Fraenkel, A

    Mor, M. and Fraenkel, A. (1984). Cayley permutations.Discrete Mathematics, 48:101–112

    work page 1984

  21. [21]

    Nkonkobe, S., B ´enyi, B., Corcino, R., and Corcino, C. (2020). A combinatorial analysis of higher order generalised geometric polynomials: A generalisation of barred preferential ar- rangements.Discrete Mathematics, 343:111729

    work page 2020

  22. [22]

    and Pylyavskyy, P

    Patrias, R. and Pylyavskyy, P . (2016). Combinatorics ofK-theory via aK-theoretic Poirier–Reutenauer bialgebra.Discrete Mathematics, 339:1095–1115

    work page 2016

  23. [23]

    Pippenger, N. (2010). The hypercube of resistors, asymptotic expansions, and preferential arrangements.Mathematics Magazine, 83

    work page 2010

  24. [24]

    and Schmidt, F

    Simion, R. and Schmidt, F. (1985). Restricted permutations.European Journal of Combinatorics, 6

    work page 1985

  25. [25]

    Sloane, N. J. A. (2025). The Online Encyclopedia of Integer Sequences.https://oeis.org

    work page 2025

  26. [26]

    Vatter, V . (2009). Finding regular insertion encodings for permutation classes.Journal of Symbolic Computation, 47

    work page 2009

  27. [27]

    Vatter, V . (2015). Permutation classes. InHandbook of Enumerative Combinatorics, pages 777–

    work page 2015

  28. [28]

    Chapman and Hall/CRC. 31

    work page