A lower bound for general t-stack sortable permutations via pattern avoidance

Authors

  • Pranav Chinmay University of Florida

DOI:

https://doi.org/10.32473/ufjur.v22i0.121801

Keywords:

pattern avoidance, stack sortability, combinatorics

Abstract

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.

Downloads

Published

2020-11-04