Sorting Cayley permutations with pattern-avoiding machines

zbMATH Open1468.05005arXiv2003.02536MaRDI QIDQ5000313FDOQ5000313

Authors: Giulio Cerbai 

Publication date: 12 July 2021

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.

Full work available at URL: https://arxiv.org/abs/2003.02536

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

zbMATH Keywords

sorting algorithms2 stacksort problem

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

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

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)