Catalan and Schroder permutations sortable by two restricted stacks

作     者：Baril, Jean-Luc Cerbai, Giulio Khalil, Carine Vajnovszki, Vincent 

作者机构：Univ Bourgogne Franche Comte LIB BP 47 870 F-21078 Dijon France Univ Firenze Dipartimento Matemat & Informat U Dini Florence Italy 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2021年第171卷

页      面：106138-106138页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：INdAMGNCS 2020 project "Combinatoria delle permutazioni  delle parole e dei grafi: algoritmi e applicazioni" 

主　　题：Stack sorting/two stacks in series Pattern avoiding permutations/machines Catalan and the Schroder numbers Combinatorial problems 

摘      要：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 Schroder numbers. (C) 2021 Published by Elsevier B.V.