Passing through a stack k times

DOI10.1142/S1793830919500034MaRDI QIDQ4621300zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 11 February 2019

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

covincular patterndata structuredescentinteger sequencepacking densitypermutation patternsortingstack

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorics of partially ordered sets (06A07)

Abstract: We consider the number of passes a permutation needs to take through a stack if we only pop the appropriate output values and start over with the remaining entries in their original order. We define a permutation $pi$ to be $k$-pass sortable if $pi$ is sortable using $k$ passes through the stack. Permutations that are $1$-pass sortable are simply the stack sortable permutations as defined by Knuth. We define the permutation class of $2$-pass sortable permutations in terms of their basis. We also show all $k$-pass sortable classes have finite bases by giving bounds on the length of a basis element of the permutation class for any positive integer $k$. Finally, we define the notion of tier of a permutation $pi$ to be the minimum number of passes after the first pass required to sort $pi$. We then give a bijection between the class of permutations of tier $t$ and a collection of integer sequences studied by Parker. This gives an exact enumeration of tier $t$ permutations of a given length and thus an exact enumeration for the class of $(t+1)$-pass sortable permutations. Finally, we give a new derivation for the generating function in Parker's thesis and an explicit formula for the coefficients.

Recommendations

• Passing through a stack \(k\) times with reversals
• Enumerating permutations sortable by \(k\) passes through a pop-stack
• Enumerating permutations sortable by k passes through a pop-stack
• scientific article; zbMATH DE number 1780162
• Sorting twice through a stack
• Permutations sortable by \(n - 4\) passes through a stack
• Stack sorting with increasing and decreasing stacks
• Stack-sorting with consecutive-pattern-avoiding stacks
• Stack-sortable permutations and beyond
• The stack-size of combinatorial tries revisited

Cites work

• A bijection on classes enumerated by the Schröder numbers
• A survey of stack-sorting disciplines
• Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
• Generalized pattern avoidance
• Generalized permutation patterns -- a short survey
• Generalized permutation patterns and a classification of the Mahonian statistics
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3492580 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Patterns in permutations and words.
• Permutations generated by a stack of depth 2 and an infinite stack in series
• Permutations generated by stacks and deques
• Permutations with forbidden subsequences and a generalized Schröder number
• Postscript: ``Permutations with forbidden subsequences and a generalized Schröder number [Discrete Mathematics 218 (2000) 121--130]
• Sorting twice through a stack
• Sorting Using Networks of Queues and Stacks
• Sorting with two ordered stacks in series.
• Two stacks in series: a decreasing stack followed by an increasing stack

Cited in

(5)

• Passing through a stack \(k\) times with reversals
• \(k\)-pop stack sortable permutations and \(2\)-avoidance
• Enumerating permutations sortable by \(k\) passes through a pop-stack
• Permutations sortable by \(n - 4\) passes through a stack
• Sorting inversion sequences

Describes a project that uses

Uses Software

• OEIS
• SageMath

This page was built for publication: Passing through a stack k times

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