A combinatorial bijection on di-sk trees (Q2121740)

Summary: 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 \[\begin{gathered} (\text{LMAX},\text{LMIN},\text{DESB},\mathsf{iar},\mathsf{comp}) \,\, \text{and}\,\, (\text{LMAX},\text{LMIN},\text{DESB},\mathsf{comp},\mathsf{iar}) \end{gathered}\] have the same distribution over separable permutations. Here for a permutation \(\pi\), \(\text{LMAX}(\pi)/\text{LMIN}(\pi)\) is the set of values of the left-to-right maxima/minima of \(\pi\) and \(\text{DESB}(\pi)\) is the set of descent bottoms of \(\pi \), while \(\mathsf{comp}(\pi)\) and \(\mathsf{iar}(\pi)\) are respectively the number of components of \(\pi\) and the length of initial ascending run of \(\pi\). Interestingly, our bijection specializes to a bijection on \(312\)-avoiding permutations, which provides (up to the classical Knuth-Richards bijection) an alternative approach to a result of \textit{M. Rubey} [Sémin. Lothar. Comb. 77, B77f, 4 p. (2018; Zbl 1396.05005)] that asserts the two triples \((\text{LMAX},\mathsf{iar},\mathsf{comp})\) and \((\text{LMAX},\mathsf{comp},\mathsf{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.