Following the footprints of what has been done with the algorithm Stacksort, we investigate the preimages of the map associated with a slightly less well known algorithm, called Queuesort. After having described an equivalent version of Queuesort, we provide a recursive description of the set of all preimages of a given permutation, which can be also translated into a recursive procedure to effectively find such preimages. We then deal with some enumerative issues. More specifically, we investigate the cardinality of the set of preimages of a given permutation, showing that all cardinalities are possible, except for 3. We also give exact enumeration results for the number of permutations having 0,1 and 2 preimages. Finally, we consider the special case of those permutations π whose set of left-to-right maxima is the disjoint union of a prefix and a suffix of π: we determine a closed formula for the number of preimages of such permutations, which involves two different incarnations of ballot numbers, and we show that our formula can be expressed as a linear combination of Catalan numbers.
Preimages under the Queuesort algorithm / Cioni L.; Ferrari L.. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - STAMPA. - 344:(2021), pp. 0-0. [10.1016/j.disc.2021.112561]
Preimages under the Queuesort algorithm
Cioni L.;Ferrari L.
2021
Abstract
Following the footprints of what has been done with the algorithm Stacksort, we investigate the preimages of the map associated with a slightly less well known algorithm, called Queuesort. After having described an equivalent version of Queuesort, we provide a recursive description of the set of all preimages of a given permutation, which can be also translated into a recursive procedure to effectively find such preimages. We then deal with some enumerative issues. More specifically, we investigate the cardinality of the set of preimages of a given permutation, showing that all cardinalities are possible, except for 3. We also give exact enumeration results for the number of permutations having 0,1 and 2 preimages. Finally, we consider the special case of those permutations π whose set of left-to-right maxima is the disjoint union of a prefix and a suffix of π: we determine a closed formula for the number of preimages of such permutations, which involves two different incarnations of ballot numbers, and we show that our formula can be expressed as a linear combination of Catalan numbers.File | Dimensione | Formato | |
---|---|---|---|
1-s2.0-S0012365X21002740-main.pdf
Accesso chiuso
Descrizione: Articolo principale
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
427.98 kB
Formato
Adobe PDF
|
427.98 kB | Adobe PDF | Richiedi una copia |
queuesort_preimages_final.pdf
accesso aperto
Descrizione: Articolo principale
Tipologia:
Versione finale referata (Postprint, Accepted manuscript)
Licenza:
Open Access
Dimensione
405.57 kB
Formato
Adobe PDF
|
405.57 kB | Adobe PDF |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.