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.

M. Barnabei, F. Bonetti, M. Silimbani (2012). Two Permutation Classes related to the Bubble Sort Operator. ELECTRONIC JOURNAL OF COMBINATORICS, 19(3), 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.
2012
M. Barnabei, F. Bonetti, M. Silimbani (2012). Two Permutation Classes related to the Bubble Sort Operator. ELECTRONIC JOURNAL OF COMBINATORICS, 19(3), 1-25.
M. Barnabei; F. Bonetti; M. Silimbani
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/126347
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 0
social impact