Sorting Cayley permutations with pattern-avoiding machines

MaRDI QIDQ5000313zbMATH OpenFDO

Authors Giulio Cerbai

Publication date 12 July 2021

Full work available at URL https://arxiv.org/abs/2003.02536, http://ajc.maths.uq.edu.au/pdf/80/ajc_v80_p322.pdf

zbMATH Keywords

sorting algorithms2 stacksort problem

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: Pattern avoiding machines were recently introduced by Claesson, Ferrari and the current author to gain a better understanding of the classical $2$-stacksort problem. In this paper we generalize these devices by allowing permutations with repeated elements, also known as Cayley permutations. The main result is a description of those patterns such that the corresponding set of sortable permutations is a class. We also show a new involution on the set of Cayley permutations, obtained by regarding a pattern-avoiding stack as an operator. Finally, we analyze two generalizations of pop-stack sorting on Cayley permutations. In both cases we describe sortable permutations in terms of pattern avoidance.

Recommendations

• Catalan and Schröder permutations sortable by two restricted stacks
• Sorting with pattern-avoiding stacks: the \(132\)-machine
• Stack sorting with restricted stacks
• Two-stack-sorting with pop stacks
• A stack and pop stack in series

Cites work

• scientific article; zbMATH DE number 3722110 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 2107707 (Why is no real title available?)
• scientific article; zbMATH DE number 7524066 (Why is no real title available?)
• A survey of stack-sorting disciplines
• Catalan and Schröder permutations sortable by two restricted stacks
• Cayley permutations
• Counting 3-stack-sortable permutations
• Enumerating permutations sortable by \(k\) passes through a pop-stack
• Mesh patterns and the expansion of permutation statistics as sums of permutation patterns
• Patterns in permutations and words.
• Permutations of a multiset avoiding permutations of length 3
• Postorder Preimages
• Priority queues and multisets
• Restricted permutations and the wreath product
• Restricted stacks as functions
• Sorted and/or sortable permutations
• Sorting twice through a stack
• Sorting with pattern-avoiding stacks: the \(132\)-machine
• Stack sorting with increasing and decreasing stacks
• Stack sorting with restricted stacks
• Stack-sorting for words
• Stack-sorting with consecutive-pattern-avoiding stacks
• Two stacks in series: a decreasing stack followed by an increasing stack
• Two-stack-sorting with pop stacks

Cited in

(13)

• Transport of patterns by Burge transpose
• Stack-sorting for Coxeter groups
• Catalan and Schröder permutations sortable by two restricted stacks
• Sorting with pattern-avoiding stacks: the \(132\)-machine
• Foot-sorting for socks
• Restricted stacks as functions
• Permuting machines and permutation patterns
• Fishburn trees
• Fast Sorting and Pattern-Avoiding Permutations
• Deterministic stack-sorting for set partitions
• Dynamical aspects of \(\sigma\)-machines
• Modified ascent sequences and Bell numbers
• Stack-sorting with consecutive-pattern-avoiding stacks

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Sorting Cayley permutations with pattern-avoiding machines

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