Open AccessA lower bound for general t-stack sortable permutations via pattern avoidance
Author(s) -
Pranav Chinmay
Publication year - 2020
Publication title -
journal of undergraduate research
Language(s) - English
Resource type - Journals
ISSN - 2638-0668
DOI - 10.32473/ufjur.v22i0.121801
Subject(s) - mathematics , stack (abstract data type) , combinatorics , upper and lower bounds , set (abstract data type) , discrete mathematics , computer science , mathematical analysis , programming language
There is no formula for general t-stack sortable permutations. Thus, we attempt to study them by establishing lower and upper bounds. Permutations that avoid certain pattern sets provide natural lower bounds. This paper presents a recurrence relation that counts the number of permutations that avoid the set (23451,24351,32451,34251,42351,43251). This establishes a lower bound on 3-stack sortable permutations. Additionally, the proof generalizes to provide lower bounds for all t-stack sortable permutations.