Geodesic
Two permutation classes related to the bubble sort operator
Marilena Barnabei1 ; Flavio Bonetti1 ; Matteo Silimbani1
1Università di Bologna Dipartimento di Matematica Italy
The electronic journal of combinatorics, Tome 19 (2012) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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$.
DOI : 10.37236/2556
Classification : 05A05, 05A15, 68P10, 68W05
Mots-clés : permutation class, sorting algorithm, permutation statistic

Marilena Barnabei  1   ; Flavio Bonetti  1   ; Matteo Silimbani  1

1 Università di Bologna Dipartimento di Matematica Italy 
@article{10_37236_2556,
     author = {Marilena Barnabei and Flavio Bonetti and Matteo Silimbani},
     title = {Two permutation classes related to the bubble sort operator},
     journal = {The electronic journal of combinatorics},
     year = {2012},
     volume = {19},
     number = {3},
     doi = {10.37236/2556},
     zbl = {1253.05005},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2556/}
}
TY  - JOUR
AU  - Marilena Barnabei
AU  - Flavio Bonetti
AU  - Matteo Silimbani
TI  - Two permutation classes related to the bubble sort operator
JO  - The electronic journal of combinatorics
PY  - 2012
VL  - 19
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2556/
DO  - 10.37236/2556
ID  - 10_37236_2556
ER  - 
%0 Journal Article
%A Marilena Barnabei
%A Flavio Bonetti
%A Matteo Silimbani
%T Two permutation classes related to the bubble sort operator
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/2556/
%R 10.37236/2556
%F 10_37236_2556
Marilena Barnabei; Flavio Bonetti; Matteo Silimbani. Two permutation classes related to the bubble sort operator. The electronic journal of combinatorics, Tome 19 (2012) no. 3. doi: 10.37236/2556

Cité par Sources :