On a conjecture concerning two-stack sortable permutations

Abstract

The two-stack sortable permutations of length $n$ are known to be equinumerous with permutations of length $n$ avoiding the dashed patterns $3\text{-}1\text{-}4\text{-}2$ and $2\text{-}41\text{-}3$. In this paper, we confirm an intriguing conjecture posed by Claesson, Kitaev, and Steingrímsson, which asserts that the quadruple $(\comp,\asc,\ldr,\rmax)$ is equidistributed on these two permutation classes. Here $\comp$ and $\asc$ count the number of components and ascents, respectively, $\ldr$ denotes the length of the initial decreasing run, and $\rmax$ denotes the number of right-to-left maxima. This is accomplished by constructing bijections between two-stack sortable permutations and $\beta (1,0)$-trees.