Subregularity in infinitely labeled generating trees of restricted permutations

2021/10/15 by Toufik Mansour, Mansour, Toufik, Reza Rastegar +3
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2110.07784

openalex publication_date 2021/10/15 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28

Abstract

In this paper, we revisit the application of generating trees to the pattern avoidance problem for permutations. In particular, we study this problem for certain general sets of patterns and propose a new procedure leveraging the FinLabel algorithm and exploiting the subregularities in the associated generating trees. We consider some general kinds of generating trees for which the FinLabel algorithm fails to determine in a finite number of iterations the generating function that enumerates the underlying class of permutations. Our procedure provides a unified approach in these cases leading to a system of equations satisfied by a certain finite set of generating functions which can be readily solved with the aid of programming.

Related

• Finitely labeled generating trees and restricted permutations
• Generating trees for permutations avoiding generalized patterns
• On the sub-permutations of pattern avoiding permutations
• Exhaustive generation for permutations avoiding a (colored) regular sets of patterns
• A generating tree with a single label for permutations avoiding the vincular pattern 1-32-4