A combinatorial bijection on di-sk trees

Abstract

A di-sk tree is a rooted binary tree whose nodes are labeled by $\oplus$ or $\ominus$, and no node has the same label as its right child. The di-sk trees are in natural bijection with separable permutations. We construct a combinatorial bijection on di-sk trees proving the two quintuples $(\LMAX,\LMIN,\DESB,\iar,\comp)$ and $(\LMAX,\LMIN,\DESB,\comp,\iar)$ have the same distribution over separable permutations. Here for a permutation $\ddot{I}€$, $\LMAX(π)/\LMIN(π)$ is the set of values of the left-to-right maxima/minima of $\ddot{I}€$ and $\DESB(π)$ is the set of descent bottoms of $\ddot{I}€$, while $\comp(π)$ and $\iar(π)$ are respectively the number of components of $\ddot{I}€$ and the length of initial ascending run of $\ddot{I}€$. Interestingly, our bijection specializes to a bijection on $312$-avoiding permutations, which provides (up to the classical {\em Knuth--Richards bijection}) an alternative approach to a result of Rubey (2016) that asserts the two triples $(\LMAX,\iar,\comp)$ and $(\LMAX,\comp,\iar)$ are equidistributed on $321$-avoiding permutations. Rubey's result is a symmetric extension of an equidistribution due to Adin--Bagno--Roichman, which implies the class of $321$-avoiding permutations with a prescribed number of components is Schur positive. Some equidistribution results for various statistics concerning tree traversal are presented in the end.

Minor revision: 20 pages, 7 figures