Stack-sorting for words

MaRDI QIDQ3300688zbMATH OpenFDO

Authors Colin Defant, Noah Kravitz

Publication date 29 July 2020

Full work available at URL https://arxiv.org/abs/1809.09158, http://ajc.maths.uq.edu.au/pdf/77/ajc_v77_p051.pdf

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Searching and sorting (68P10) Combinatorics on words (68R15)

Abstract: We introduce operators $mathsfhare$ and $mathsftortoise$, which act on words as natural generalizations of West's stack-sorting map. We show that the heuristically slower algorithm $mathsftortoise$ can sort words arbitrarily faster than its counterpart $mathsfhare$. We then generalize the combinatorial objects known as valid hook configurations in order to find a method for computing the number of preimages of any word under these two operators. We relate the question of determining which words are sortable by $mathsfhare$ and $mathsftortoise$ to more classical problems in pattern avoidance, and we derive a recurrence for the number of words with a fixed number of copies of each letter (permutations of a multiset) that are sortable by each map. In particular, we use generating trees to prove that the $ell$-uniform words on the alphabet $[n]$ that avoid the patterns $231$ and $221$ are counted by the $(ell+1)$-Catalan number $frac1elln+1(ell+1)nchoosen$. We conclude with several open problems and conjectures.

Recommendations

• Sorting and preimages of pattern classes
• Stack-sorting with consecutive-pattern-avoiding stacks
• Stack words and a bound for 3-stack sortable permutations
• Stack-sortable permutations and beyond
• A survey of stack sortable permutations

Cites work

• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 5557896 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Avoiding patterns of length three in compositions and multiset permutations
• Catalan intervals and uniquely sorted permutations
• Combinatorics of Compositions and Words
• Combinatorics of permutations
• Counting 3-stack-sortable permutations
• Fertility numbers
• Fighting fish
• Fighting fish and two-stack sortable permutations
• Finite automata and pattern avoidance in words
• Finitely labeled generating trees and restricted permutations
• Further bijections to pattern-avoiding valid hook configurations
• Generating functions for generating trees
• Generating trees and forbidden subsequences
• Generating trees and the Catalan and Schröder numbers
• Pattern avoidance in compositions and multiset permutations
• Patterns in permutations and words.
• Permutations of a multiset avoiding permutations of length 3
• Permutations with forbidden subsequences and nonseparable planar maps
• Postorder Preimages
• Preimages under the stack-sorting algorithm
• Priority queues and multisets
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
• Restricted 132-avoiding \(k\)-ary words, Chebyshev polynomials, and continued fractions
• Some Generalizations of Vandermonde's Convolution
• Sorted and/or sortable permutations
• Stack-sorting, set partitions, and Lassalle's sequence
• Staircases, dominoes, and the growth rate of 1324-avoiders
• The number of Baxter permutations
• Words restricted by patterns with at most 2 distinct letters

Cited in

(8)

• Counting 3-stack-sortable permutations
• A lift of West's stack-sorting map to partition diagrams
• Pushes in words -- a primitive sorting algorithm
• Foot-sorting for socks
• Sorting Cayley permutations with pattern-avoiding machines
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Stack-sorting, set partitions, and Lassalle's sequence
• Deterministic stack-sorting for set partitions

This page was built for publication: Stack-sorting for words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3300688)