Geodesic
Consecutive patterns in restricted permutations and involutions
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 3.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2019_21_3_a15,
     author = {Barnabei, M. and Bonetti, F. and Castronuovo, N. and Silimbani, M.},
     title = {Consecutive patterns in restricted permutations and involutions},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2019},
     doi = {10.23638/DMTCS-21-3-21},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-21/}
}
TY  - JOUR
AU  - Barnabei, M.
AU  - Bonetti, F.
AU  - Castronuovo, N.
AU  - Silimbani, M.
TI  - Consecutive patterns in restricted permutations and involutions
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-21/
DO  - 10.23638/DMTCS-21-3-21
LA  - en
ID  - DMTCS_2019_21_3_a15
ER  - 
%0 Journal Article
%A Barnabei, M.
%A Bonetti, F.
%A Castronuovo, N.
%A Silimbani, M.
%T Consecutive patterns in restricted permutations and involutions
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-21/
%R 10.23638/DMTCS-21-3-21
%G en
%F DMTCS_2019_21_3_a15
Barnabei, M.; Bonetti, F.; Castronuovo, N.; Silimbani, M. Consecutive patterns in restricted permutations and involutions. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 3. doi : 10.23638/DMTCS-21-3-21. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-21/

Cité par Sources :