math.CO

# Title: 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 which proves that the two quadruples $(\LMAX,\DESB,\iar,\comp)$ and $(\LMAX,\DESB,\comp,\iar)$ have the same distribution over separable permutations. Here for a permutation $\pi$, $\LMAX(\pi)$ is the set of values of the left-to-right maxima of $\pi$ and $\DESB(\pi)$ is the set of descent bottoms of $\pi$, while $\comp(\pi)$ and $\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 {\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.
 Comments: 20 pages, 7 figures Subjects: Combinatorics (math.CO) Cite as: arXiv:2011.11302 [math.CO] (or arXiv:2011.11302v1 [math.CO] for this version)

## Submission history

From: Zhicong Lin [view email]
[v1] Mon, 23 Nov 2020 09:46:07 GMT (28kb)

Link back to: arXiv, form interface, contact.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8358956,"math_prob":0.9948236,"size":1677,"snap":"2021-04-2021-17","text_gpt3_token_len":432,"char_repetition_ratio":0.115959354,"word_repetition_ratio":0.008547009,"special_character_ratio":0.25283244,"punctuation_ratio":0.11881188,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99590683,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-01-20T06:09:46Z\",\"WARC-Record-ID\":\"<urn:uuid:89dd9a47-2cd5-42ee-a6ec-2aede4e70ac3>\",\"Content-Length\":\"16320\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:af780ead-de2b-4171-bdb8-804fd9a544bc>\",\"WARC-Concurrent-To\":\"<urn:uuid:3b546057-ab47-45bb-ad1a-3d08119912ab>\",\"WARC-IP-Address\":\"128.84.21.203\",\"WARC-Target-URI\":\"http://export.arxiv.org/abs/2011.11302\",\"WARC-Payload-Digest\":\"sha1:COF32H5CPF6WKGO22SRJY7GIAQODGJTU\",\"WARC-Block-Digest\":\"sha1:YUFH22VTKL2BOVSGHNZARH662YKZSJYY\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-04/CC-MAIN-2021-04_segments_1610703519923.26_warc_CC-MAIN-20210120054203-20210120084203-00560.warc.gz\"}"}