A permutation π avoids the subpattern τ iff π has no subsequence having all the same pairwise comparisons as τ, and we write π ∈ S(τ). We examine the classes of permutations, S(321), S(321, 31̄42) and S(4231, 4132), enumerated, respectively by the famous Catalan, Motzkin and Schröder number sequences. We determine their generating functions according to their length, number of active sites and inversion number. We also find the average inversion number for each class. Finally, we describe some bijections between these classes of permutations and some classes of parallelogram polyominoes, from which we deduce some relations between the parameters of Motzkin and Schröder permutations.
Some permutation with forbidden subsequences and their inversion number / E. BARCUCCI; A. DEL LUNGO; E. PERGOLA; R. PINZANI. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - STAMPA. - 234:(2001), pp. 1-15. [10.1016/S0012-365X(00)00359-9]
Some permutation with forbidden subsequences and their inversion number
BARCUCCI, ELENA;PERGOLA, ELISA;PINZANI, RENZO
2001
Abstract
A permutation π avoids the subpattern τ iff π has no subsequence having all the same pairwise comparisons as τ, and we write π ∈ S(τ). We examine the classes of permutations, S(321), S(321, 31̄42) and S(4231, 4132), enumerated, respectively by the famous Catalan, Motzkin and Schröder number sequences. We determine their generating functions according to their length, number of active sites and inversion number. We also find the average inversion number for each class. Finally, we describe some bijections between these classes of permutations and some classes of parallelogram polyominoes, from which we deduce some relations between the parameters of Motzkin and Schröder permutations.I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.