Sorting with pattern-avoiding stacks: the 132-machine

DOI10.37236/9642MaRDI QIDQ2194083zbMATH OpenOpenAlexFDO

Authors Giulio Cerbai, Anders Claesson, Einar Steingrímsson, L. Ferrari

Publication date 25 August 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

pattern-avoiding sorting machines

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Searching and sorting (68P10) Partitions of sets (05A18) Factorials, binomial coefficients, combinatorial functions (05A10) Combinatorial identities, bijective combinatorics (05A19)

Abstract: This paper continues the analysis of the pattern-avoiding sorting machines recently introduced by Cerbai, Claesson and Ferrari [CCF]. These devices consist of two stacks, through which a permutation is passed in order to sort it, where the content of each stack must at all times avoid a certain pattern. Here we characterize and enumerate the set of permutations that can be sorted when the first stack is $132$-avoiding, solving one of the open problems proposed in [CCF]. To that end we present several connections with other well known combinatorial objects, such as lattice paths and restricted growth functions (which encode set partitions). We also provide new proofs for the enumeration of some sets of pattern-avoiding restricted growth functions and we expect that the tools introduced can be fruitfully employed to get further similar results.

Recommendations

• Stack sorting with restricted stacks
• Catalan and Schröder permutations sortable by two restricted stacks
• Sorting Cayley permutations with pattern-avoiding machines
• Two-stack-sorting with pop stacks
• Two stacks in series: a decreasing stack followed by an increasing stack

Cites work

• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Combinatorial aspects of continued fractions
• Dyck path enumeration
• ECO:a methodology for the enumeration of combinatorial objects
• Enumerative results on the Schröder pattern poset
• Mesh patterns and the expansion of permutation statistics as sums of permutation patterns
• On pattern-avoiding partitions
• Restricted growth function patterns and statistics
• Riordan arrays, generalized Narayana triangles, and series reversion
• Stack sorting with restricted stacks
• Two stacks in series: a decreasing stack followed by an increasing stack

Cited in

(9)

• Sorting with a popqueue
• Stack-sorting for Coxeter groups
• Sorting Cayley permutations with pattern-avoiding machines
• Catalan and Schröder permutations sortable by two restricted stacks
• Restricted stacks as functions
• Stack sorting with restricted stacks
• Dynamical aspects of \(\sigma\)-machines
• Stack-sorting with consecutive-pattern-avoiding stacks
• Restricted patience sorting and barred pattern avoidance

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Sorting with pattern-avoiding stacks: the \(132\)-machine

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