Two permutation classes related to the bubble sort operator
Summary: We introduce the dual bubble sort operator \(\hat{B}\) (a sorting algorithm such that, if \(\sigma=\alpha\,1\,\beta\) is a permutation, then \(\hat{B}(\sigma)=1\,\alpha\,\hat{B} (\beta))\) and consider the set of permutations sorted by the composition \(\hat{B}B\), where \(B\) is the classical bubble sort operator. We show that this set is a permutation class and we determine the generating function of the descent and fixed point distributions over this class. Afterwards, we characterize the same distributions over the set of permutations that are sorted by both \(\hat{B}^2\) and \(B^2\).
- Bubblesort, stacksort and their duals
- On the inverse image of pattern classes under bubble sort
- Sorted and/or sortable permutations
- Permutation classes
- Sorting permutations by limited-size operations
- Stack-sorting preimages of permutation classes
- Permutations sortable by two stacks in series
- Permutations sortable by deques and by two stacks in parallel
- scientific article; zbMATH DE number 910920
- Preimages under the bubblesort operator
- Enumeration of standard Young tableaux of shifted strips with constant width
- Bubblesort, stacksort and their duals
- Descent polynomials for \(k\) bubble-sortable permutations of type B
- On the inverse image of pattern classes under bubble sort
- Operators of equivalent sorting power and related Wilf-equivalences
- Making bubblesort recursive
This page was built for publication: Two permutation classes related to the bubble sort operator
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456356)
