It is well-known that the set of involutions of the symmetric group corresponds bijectively - by the Foata map - to the set of -permutations that avoid the two vincular patterns 123, 132. We consider a bijection Γ from the set to the set of histoires de Laguerre, namely, bicolored Motzkin paths with labelled steps, and study its properties when restricted to (123,132). In particular, we show that the set (123,132) of permutations that avoids the consecutive pattern 123 and the classical pattern 132 corresponds via Γ to the set of Motzkin paths, while its image under is the set of restricted involutions (3412). We exploit these results to determine the joint distribution of the statistics des and inv over (123,132) and over (3412). Moreover, we determine the distribution in these two sets of every consecutive pattern of length three. To this aim, we use a modified version of the well-known Goulden-Jacson cluster method.

Consecutive patterns in restricted permutations and involutions / Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, Matteo Silimbani. - In: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE. - ISSN 1365-8050. - ELETTRONICO. - 21:3(2019), pp. 1-21. [10.23638/DMTCS-21-3-21]

Consecutive patterns in restricted permutations and involutions

Marilena Barnabei;Flavio Bonetti;Niccolò Castronuovo;Matteo Silimbani
2019

Abstract

It is well-known that the set of involutions of the symmetric group corresponds bijectively - by the Foata map - to the set of -permutations that avoid the two vincular patterns 123, 132. We consider a bijection Γ from the set to the set of histoires de Laguerre, namely, bicolored Motzkin paths with labelled steps, and study its properties when restricted to (123,132). In particular, we show that the set (123,132) of permutations that avoids the consecutive pattern 123 and the classical pattern 132 corresponds via Γ to the set of Motzkin paths, while its image under is the set of restricted involutions (3412). We exploit these results to determine the joint distribution of the statistics des and inv over (123,132) and over (3412). Moreover, we determine the distribution in these two sets of every consecutive pattern of length three. To this aim, we use a modified version of the well-known Goulden-Jacson cluster method.
2019
Consecutive patterns in restricted permutations and involutions / Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, Matteo Silimbani. - In: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE. - ISSN 1365-8050. - ELETTRONICO. - 21:3(2019), pp. 1-21. [10.23638/DMTCS-21-3-21]
Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, Matteo Silimbani
File in questo prodotto:
File Dimensione Formato  
consecutive.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione 208.75 kB
Formato Adobe PDF
208.75 kB Adobe PDF Visualizza/Apri

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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/688760
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact