Roller Coaster Permutations and Partition Numbers

Abstract

This paper explores the partition properties of roller coaster permutations, a class of permutations characterized by maximizing the number of alternating runs in all subsequences. We establish a connection between the structure of these permutations and their partition numbers, defined as the minimum number of monotonic subsequences required to cover the permutation. Our main result provides a theoretical upper bound for the partition number of a roller coaster permutation of length $n$, given by $P_{max}(n)\le \lfloor \frac{\lceil \frac{n-2}{2}\rceil }{2}\rfloor +2$. We further present experimental data for $n<15$ that suggests this bound is nearly sharp.