Pattern avoiding machines were introduced recently by Claesson, Cerbai and Ferrari as a particular case of the two-stacks in series sorting device. They consist of two restricted stacks in series, ruled by a right-greedy procedure and the stacks avoid some specified patterns. Some of the obtained results have been further generalized to Cayley permutations by Cerbai, specialized to particular patterns by Defant and Zheng, or considered in the context of functions over the symmetric group by Berlow. In this work we study pattern avoiding machines where the first stack avoids a pair of patterns of length 3 and investigate those pairs for which sortable permutations are counted by the (binomial transform of the) Catalan numbers and the Schröder numbers.

Catalan and Schröder permutations sortable by two restricted stacks / Baril, Jean-Luc; Cerbai, Giulio; Khalil, Carine; Vajnovszki, Vincent. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - ELETTRONICO. - 171:(2021), pp. 106138-106138. [10.1016/j.ipl.2021.106138]

Catalan and Schröder permutations sortable by two restricted stacks

Cerbai, Giulio;
2021

Abstract

Pattern avoiding machines were introduced recently by Claesson, Cerbai and Ferrari as a particular case of the two-stacks in series sorting device. They consist of two restricted stacks in series, ruled by a right-greedy procedure and the stacks avoid some specified patterns. Some of the obtained results have been further generalized to Cayley permutations by Cerbai, specialized to particular patterns by Defant and Zheng, or considered in the context of functions over the symmetric group by Berlow. In this work we study pattern avoiding machines where the first stack avoids a pair of patterns of length 3 and investigate those pairs for which sortable permutations are counted by the (binomial transform of the) Catalan numbers and the Schröder numbers.
2021
171
106138
106138
Baril, Jean-Luc; Cerbai, Giulio; Khalil, Carine; Vajnovszki, Vincent
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0020019021000533-main.pdf

accesso aperto

Tipologia: Pdf editoriale (Version of record)
Licenza: Open Access
Dimensione 351.24 kB
Formato Adobe PDF
351.24 kB Adobe PDF

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

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1237635
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact