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.
2001
234
1
15
E. BARCUCCI; A. DEL LUNGO; E. PERGOLA; R. PINZANI
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/311638
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 11
social impact