Preimages under the bubblesort operator

DOI10.37236/11390MaRDI QIDQ2112565zbMATH OpenOpenAlexFDO

Authors Mathilde Bouvel, Lapo Cioni, L. Ferrari

Publication date 11 January 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2204.12936

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

average height of leavesaverage height of nodessorting operators

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Trees (05C05)

Abstract: We study preimages of permutations under the bubblesort operator $mathbfB$. We achieve a description of these preimages much more complete than what is known for the more complicated sorting operators $mathbfS$ (stacksort) and $mathbfQ$ (queuesort). We describe explicitly the set of preimages under $mathbfB$ of any permutation $pi$ from the left-to-right maxima of $pi$, 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 $mathbfB$ (the root being the identity permutation), and we present several properties of these trees. In particular, for each permutation $pi$, we show how the subtree of $T_n$ rooted at $pi$ is determined by the number of left-to-right maxima of $pi$ and the length of the longest suffix of left-to-right maxima of $pi$. 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$.

Review text

Summary: We study preimages of permutations under the bubblesort operator \(\mathcal{B}\). We achieve a description of these preimages much more complete than what is known for the more complicated sorting operators \(\mathcal{S}\) (stacksort) and \(\mathcal{Q}\) (queuesort). We describe explicitly the set of preimages under \(\mathcal{B}\) of any permutation \(\pi\) from the left-to-right maxima of \(\pi\), 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 \(\mathcal{B}\) (the root being the identity permutation), and we present several properties of these trees. In particular, for each permutation \(\pi\), we show how the subtree of \(T_n\) rooted at \(\pi\) is determined by the number of left-to-right maxima of \(\pi\) and the length of the longest suffix of left-to-right maxima of \(\pi\). 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\).

Recommendations

• Preimages under the Queuesort algorithm
• Two permutation classes related to the bubble sort operator
• Preimages under the stack-sorting algorithm
• On the inverse image of pattern classes under bubble sort
• Bubblesort, stacksort and their duals

Cites work

• A survey of stack-sorting disciplines
• Average-case analysis of algorithms using Kolmogorov complexity
• ECO:a methodology for the enumeration of combinatorial objects
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Fertility monotonicity and average complexity of the stack-sorting map
• Fertility numbers
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• On the inverse image of pattern classes under bubble sort
• Polyurethane toggles
• Preimages under the Queuesort algorithm
• Preimages under the stack-sorting algorithm
• Quantifying noninvertibility in discrete dynamical systems
• Some applications arising from the interactions between the theory of Catalan-like numbers and the ECO method.
• Sorted and/or sortable permutations
• Sorting and preimages of pattern classes
• Stack-sorting preimages of permutation classes
• Stack-sorting, set partitions, and Lassalle's sequence

Cited in

(6)

• Preimages under the Queuesort algorithm
• Postorder Preimages
• On the inverse image of pattern classes under bubble sort
• Sorting with a popqueue
• Sorting permutations using a pop stack with a bypass
• Fidelity decay and error accumulation in random quantum circuits

This page was built for publication: Preimages under the bubblesort operator

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2112565)