We study preimages of permutations under the bubblesort operator B. We achieve a description of these preimages much more complete than what is known for the more complicated sorting operators S (stacksort) and Q (queuesort). We describe explicitly the set of preimages under B of any permutation π from the left-to-right maxima of π, showing that there are 2^{k−1} such preimages if k is the number of these left-to-right maxima. We further consider, for each n, the tree T_n recording all permutations of size n in its nodes, in which an edge from child to parent corresponds to an application of B (the root being the identity permutation), and we present several properties of these trees. In particular, for each permutation π, we show how the subtree of T_n rooted at π is determined by the number of left-to-right maxima of π and the length of the longest suffix of left-to-right maxima of π. Building on this result, we determine the number of nodes and leaves at every height in such trees, and we recover (resp. obtain) the average height of nodes (resp. leaves) in T_n.

Preimages under the Bubblesort Operator / Bouvel, Mathilde; Cioni, Lapo; Ferrari, Luca. - In: ELECTRONIC JOURNAL OF COMBINATORICS. - ISSN 1077-8926. - ELETTRONICO. - 29:(2022), pp. P4.32.0-P4.32.0. [10.37236/11390]

### Preimages under the Bubblesort Operator

#### Abstract

We study preimages of permutations under the bubblesort operator B. We achieve a description of these preimages much more complete than what is known for the more complicated sorting operators S (stacksort) and Q (queuesort). We describe explicitly the set of preimages under B of any permutation π from the left-to-right maxima of π, showing that there are 2^{k−1} such preimages if k is the number of these left-to-right maxima. We further consider, for each n, the tree T_n recording all permutations of size n in its nodes, in which an edge from child to parent corresponds to an application of B (the root being the identity permutation), and we present several properties of these trees. In particular, for each permutation π, we show how the subtree of T_n rooted at π is determined by the number of left-to-right maxima of π and the length of the longest suffix of left-to-right maxima of π. Building on this result, we determine the number of nodes and leaves at every height in such trees, and we recover (resp. obtain) the average height of nodes (resp. leaves) in T_n.
##### Scheda breve Scheda completa Scheda completa (DC) 2022
29
0
0
Bouvel, Mathilde; Cioni, Lapo; Ferrari, Luca
File in questo prodotto:
File
11390-PDF file-42716-2-10-20221111.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Pdf editoriale (Version of record)
Licenza: Creative commons
Dimensione 356.66 kB
Utilizza questo identificatore per citare o creare un link a questa risorsa: `https://hdl.handle.net/2158/1290704`
• ND
• 0
• ND
{"ft_lang_label":"__label__en","ft_lang_prob":0.8165327,"math_prob":0.93968636,"size":2847,"snap":"2023-14-2023-23","text_gpt3_token_len":716,"char_repetition_ratio":0.12099894,"word_repetition_ratio":0.8017621,"special_character_ratio":0.24060415,"punctuation_ratio":0.11827957,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9854933,"pos_list":[0,1,2,3,4,5,6,7,8],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-03-30T08:41:19Z\",\"WARC-Record-ID\":\"<urn:uuid:555c6dd9-6dab-46f4-83f1-6420201825f0>\",\"Content-Length\":\"51220\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:b5188b12-fea9-48e4-aa3a-5fe155080fda>\",\"WARC-Concurrent-To\":\"<urn:uuid:40c5dd73-f0b5-4098-9cb5-87c695f87371>\",\"WARC-IP-Address\":\"130.186.29.4\",\"WARC-Target-URI\":\"https://flore.unifi.it/handle/2158/1290704\",\"WARC-Payload-Digest\":\"sha1:VFVTQE445BZU4CC7O42PJ5RINBCYNQ6M\",\"WARC-Block-Digest\":\"sha1:3OLFHG2LINFAKQNBITG5A3NAD65MVKSG\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-14/CC-MAIN-2023-14_segments_1679296949107.48_warc_CC-MAIN-20230330070451-20230330100451-00438.warc.gz\"}"}