We introduce the Dual Bubble Sort operator Bˆ (a sorting algorithm such that, if σ=α1β is a permutation, then Bˆ(σ)=1αBˆ(β)) and consider the set of permutations sorted by the composition 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 Bˆ2 and B2.
Two Permutation Classes related to the Bubble Sort Operator / M. Barnabei; F. Bonetti; M. Silimbani. - In: ELECTRONIC JOURNAL OF COMBINATORICS. - ISSN 1077-8926. - ELETTRONICO. - 19:3(2012), pp. 1-25.
Two Permutation Classes related to the Bubble Sort Operator
BARNABEI, MARILENA;BONETTI, FLAVIO;SILIMBANI, MATTEO
2012
Abstract
We introduce the Dual Bubble Sort operator Bˆ (a sorting algorithm such that, if σ=α1β is a permutation, then Bˆ(σ)=1αBˆ(β)) and consider the set of permutations sorted by the composition 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 Bˆ2 and B2.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
