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.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.