Stack sorting with restricted stacks

DOI10.1016/J.JCTA.2020.105230zbMATH Open1435.05004arXiv1907.08142OpenAlexW3006907031MaRDI QIDQ2306002FDOQ2306002

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)

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.

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

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

zbMATH Keywords

generating functionCatalan numberspermutation patternstacksort

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?)
• 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
• Title not available (Why is that?)
• Discrete excursions
• On iterated generating functions for integer sequences, and Catalan polynomials
• Enumerative results on the Schröder pattern poset

Cited In (25)

• Sorting with a popqueue
• Sorting with pattern-avoiding stacks: the \(132\)-machine
• Two stacks in series: a decreasing stack followed by an increasing stack
• A stack and pop stack in series
• Generating permutations with restricted containers
• Sorting twice through a stack
• Modified ascent sequences and Bell numbers
• A lift of West's stack-sorting map to partition diagrams
• Pop-stack-sorting for Coxeter groups
• Stack-sorting for Coxeter groups
• Characterization and enumeration of preimages under the \texttt{Queuesort} algorithm
• Stack sorting with increasing and decreasing stacks
• Foot-sorting for socks
• Highly sorted permutations with respect to a 312-avoiding stack
• Sorting Cayley permutations with pattern-avoiding machines
• Sorting with forbidden intermediates
• Dynamical aspects of \(\sigma\)-machines
• A survey of stack-sorting disciplines
• Deterministic stack-sorting for set partitions
• Stack-sorting with consecutive-pattern-avoiding stacks
• Catalan and Schröder permutations sortable by two restricted stacks
• Two-stack-sorting with pop stacks
• Preimages under the Queuesort algorithm
• Restricted stacks as functions
• Transport of patterns by Burge transpose

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)