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.

Marilena Barnabei, F.B. (2019). Consecutive patterns in restricted permutations and involutions. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 21(3), 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
Marilena Barnabei, F.B. (2019). Consecutive patterns in restricted permutations and involutions. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 21(3), 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