2005/12/06 by Alexander Burstein, Burstein, Alexander, Isaiah Lankham +1
Computer Science · #05A05 #05A15 #05A18 (Primary) #05E10 (Secondary) #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.math/0512122
openalex publication_date 2005/12/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Patience Sorting is a combinatorial algorithm that can be viewed as an iterated, non-recursive form of the Schensted Insertion Algorithm. In recent work the authors have shown that Patience Sorting provides an algorithmic description for permutations avoiding the barred (generalized) permutation pattern 3-1-42. Motivated by this and a recently formulated geometric form for Patience Sorting in terms of certain intersecting lattice paths, we study the related themes of restricted input and avoidance of similar barred permutation patterns. One such result is to characterize those permutations for which Patience Sorting is an invertible algorithm as the set of permutations simultaneously avoiding the barred patterns 3-1-42 and 3-1-24. We then enumerate this avoidance set, which involves convolved Fibonacci numbers.