Stack sorting with restricted stacks

DOI10.1016/J.JCTA.2020.105230MaRDI QIDQ2306002zbMATH OpenOpenAlexFDO

Authors Giulio Cerbai, Anders Claesson, L. Ferrari

Publication date 20 March 2020

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

Catalan numbersgenerating functionpermutation patternstacksort

Mathematics Subject Classification ID

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

Abstract: The (classical) problem of characterizing and enumerating permutations that can be sorted using two stacks connected in series is still largely open. In the present paper we address a related problem, in which we impose restrictions both on the procedure and on the stacks. More precisely, we consider a greedy algorithm where we perform the rightmost legal operation (here "rightmost" refers to the usual representation of stack sorting problems). Moreover, the first stack is required to be $sigma$-avoiding, for some permutation $sigma$, meaning that, at each step, the elements maintained in the stack avoid the pattern $sigma$ when read from top to bottom. Since the set of permutations which can be sorted by such a device (which we call $sigma$-machine) is not always a class, it would be interesting to understand when it happens. We will prove that the set of $sigma$-machines whose associated sortable permutations are not a class is counted by Catalan numbers. Moreover, we will analyze two specific $sigma$-machines in full details (namely when $sigma=321$ and $sigma=123$), providing for each of them a complete characterization and enumeration of sortable permutations.

Recommendations

• Sorting with pattern-avoiding stacks: the 132-machine
• Catalan and Schröder permutations sortable by two restricted stacks
• Two stacks in series: a decreasing stack followed by an increasing stack
• Restricted stacks as functions
• Stack sorting with increasing and decreasing stacks

Cites work

• Discrete excursions
• Enumerative results on the Schröder pattern poset
• scientific article; zbMATH DE number 2186902 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• On iterated generating functions for integer sequences, and Catalan polynomials
• Permutations with restricted patterns and Dyck paths
• Sorting with two ordered stacks in series.
• Two stacks in series: a decreasing stack followed by an increasing stack

Cited in

(35)

• A survey of stack-sorting disciplines
• Generating permutations with restricted containers
• Preimages under the Queuesort algorithm
• Restricted stacks as functions
• Catalan and Schröder permutations sortable by two restricted stacks
• Stack-sorting with consecutive-pattern-avoiding stacks
• Transport of patterns by Burge transpose
• Sorting with pattern-avoiding stacks: the 132-machine
• Stack sorting with increasing and decreasing stacks
• A stack and pop stack in series
• Two stacks in series: a decreasing stack followed by an increasing stack
• Sorting Cayley permutations with pattern-avoiding machines
• Pop-stack-sorting for Coxeter groups
• Stack-sorting for Coxeter groups
• Two-stack-sorting with pop stacks
• Highly sorted permutations with respect to a 312-avoiding stack
• Dynamical aspects of \(\sigma\)-machines
• A lift of West's stack-sorting map to partition diagrams
• Sorting with a popqueue
• Characterization and enumeration of preimages under the \texttt{Queuesort} algorithm
• Foot-sorting for socks
• Modified ascent sequences and Bell numbers
• Deterministic stack-sorting for set partitions
• Periodic points of consecutive-pattern-avoiding stack-sorting maps
• Cyclic-pattern-avoiding stacks
• Stack-sorting with stacks avoiding vincular patterns
• Sorting twice through a stack
• Partially restricted stacks as functions
• The order of the (123, 132)-avoiding stack sort
• Pattern-avoiding modified ascent sequences
• Descent generating polynomials for (n - 3)- and (n - 4)-stack-sortable (pattern-avoiding) permutations
• A numerical study of L-convex polyominoes and 201-avoiding ascent sequences
• Sorting inversion sequences
• On a conjecture on pattern-avoiding machines
• Set partitions that require a maximum number of sorts through the aba-avoiding stack

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Stack sorting with restricted stacks

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