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) Factorials, binomial coefficients, combinatorial functions (05A10) Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Combinatorial identities, bijective combinatorics (05A19) Searching and sorting (68P10)

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

• 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
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• 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

(13)

• Restricted stacks as functions
• Catalan and Schröder permutations sortable by two restricted stacks
• Stack-sorting with consecutive-pattern-avoiding stacks
• Stack sorting with restricted stacks
• Restricted patience sorting and barred pattern avoidance
• Sorting Cayley permutations with pattern-avoiding machines
• Stack-sorting for Coxeter groups
• Dynamical aspects of \(\sigma\)-machines
• Sorting with a popqueue
• Periodic points of consecutive-pattern-avoiding stack-sorting maps
• Stack-sorting with stacks avoiding vincular patterns
• Pattern-avoiding modified ascent sequences
• On a conjecture on pattern-avoiding machines

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)