Sorting with pattern-avoiding stacks: the 132-machine

DOI10.37236/9642zbMATH Open1446.05003arXiv2006.05692OpenAlexW3083001871MaRDI QIDQ2194083FDOQ2194083

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)

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.

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

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

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)

Cites Work

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

Cited In (9)

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

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)