A bijection on classes enumerated by the Schröder numbers

zbMATH Open1400.05015arXiv1511.00189MaRDI QIDQ4557006FDOQ4557006

Authors:

Publication date: 28 November 2018

Abstract: We consider a sorting machine consisting of two stacks in series where the first stack has the added restriction that entries in the stack must be in decreasing order from top to bottom. The class of permutations sortable by this machine are known to be enumerated by the Schr"oder numbers. In this paper, we give a bijection between these sortable permutations of length $n$ and Schr"oder paths -- the lattice paths from $(0,0)$ to $(n-1,n-1)$ composed of East steps $(1,0)$, North steps $(0,1)$, and Diagonal steps $(1,1)$ that travel weakly below the line $y=x$.

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

Recommendations

• Two stacks in series: a decreasing stack followed by an increasing stack
• A weight-preserving bijection between Schröder paths and Schröder permutations
• Lattice paths and \((n - 2)\)-stack sortable permutations
• Two-stack-sorting with pop stacks
• Catalan and Schröder permutations sortable by two restricted stacks

zbMATH Keywords

data structurelattice pathsortingstackpermutation patternSchröder number

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Searching and sorting (68P10)

Cited In (2)

• Two stacks in series: a decreasing stack followed by an increasing stack
• Passing through a stack k times

This page was built for publication: A bijection on classes enumerated by the Schröder numbers

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