M. Barnabei ; F. Bonetti ; N. Castronuovo ; M. Silimbani - Consecutive patterns in restricted permutations and involutions

dmtcs:5175 - Discrete Mathematics & Theoretical Computer Science, June 5, 2019, Vol. 21 no. 3 - https://doi.org/10.23638/DMTCS-21-3-21
Consecutive patterns in restricted permutations and involutionsArticle

Authors: M. Barnabei ; F. Bonetti ; N. Castronuovo ; M. Silimbani

    It is well-known that the set $\mathbf I_n$ of involutions of the symmetric group $\mathbf S_n$ corresponds bijectively - by the Foata map $F$ - to the set of $n$-permutations that avoid the two vincular patterns $\underline{123},$ $\underline{132}.$ We consider a bijection $\Gamma$ from the set $\mathbf S_n$ to the set of histoires de Laguerre, namely, bicolored Motzkin paths with labelled steps, and study its properties when restricted to $\mathbf S_n(1\underline{23},1\underline{32}).$ In particular, we show that the set $\mathbf S_n(\underline{123},{132})$ of permutations that avoids the consecutive pattern $\underline{123}$ and the classical pattern $132$ corresponds via $\Gamma$ to the set of Motzkin paths, while its image under $F$ is the set of restricted involutions $\mathbf I_n(3412).$ We exploit these results to determine the joint distribution of the statistics des and inv over $\mathbf S_n(\underline{123},{132})$ and over $\mathbf I_n(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.

    Volume: Vol. 21 no. 3
    Section: Combinatorics
    Published on: June 5, 2019
    Accepted on: May 17, 2019
    Submitted on: February 7, 2019
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 503 times.
    This article's PDF has been downloaded 256 times.