A bijection on classes enumerated by the Schröder numbers

MaRDI QIDQ4557006zbMATH OpenFDO

Authors

Publication date 28 November 2018

Full work available at URL https://arxiv.org/abs/1511.00189, https://dmtcs.episciences.org/3790/pdf

zbMATH Keywords

data structurelattice pathpermutation patternSchröder numbersortingstack

Mathematics Subject Classification ID

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

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$.

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

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)