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.

Metrics

Metrics Loading ...

Downloads

Published

2020-11-04

Issue

Vol. 22 (2020): UF Journal of Undergraduate Research

Section

STEM & Medicine

License

Some journals stipulate that submitted articles cannot be under consideration for publication or published in another journal. The student-author and mentor have the option of determining which journal the paper will be submitted to first. UF JUR accepts papers that have been published in other journals or might be published in the future. It is the responsibility of the student-author and mentor to determine whether another journal will accept a paper that has been published in UF JUR.