The insertion encoding of restricted growth functions

2025/10/20 by Bean, Christian, Bell, Paul C., Ollson, Abigail
#05 #Combinatorics (math.CO) #FOS: Mathematics #G.2.1

paper · doi:10.48550/arxiv.2510.17359

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.

Citations

• Richardson tableaux and noncrossing partial matchings
• The insertion encoding of Cayley permutations
• Patterns in words of ordered set partitions
• Restricted growth function patterns and statistics
• An algorithm computing combinatorial specifications of permutation classes
• Pattern avoidance in ordered set partitions and words
• Ordered Partitions Avoiding a Permutation of Length 3
• Pattern Avoidance in Ordered Set Partitions
• Geometric grid classes of permutations
• Enumeration schemes for vincular patterns
• Mesh patterns and the expansion of permutation statistics as sums of permutation patterns
• A unification of permutation patterns related to Schubert varieties
• k-distant crossings and nestings of matchings and partitions
• Set partition statistics and q-Fibonacci numbers
• On pattern-avoiding partitions
• Pattern Avoidance in Set Partitions
• Avoidance of Partitions of a Three-element Set
• Grid classes and the Fibonacci dichotomy for restricted permutations
• Simple permutations and pattern restricted permutations

Related

• The insertion encoding of Cayley permutations
• Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding
• Restricted growth function patterns and statistics
• Set Partitions and Other Bell Number Enumerated Objects
• Combinatorial statistics on restricted growth functions containing a pattern exactly k times