Geodesic
Right-jumps and pattern avoiding permutations
Discrete mathematics & theoretical computer science, Permutation Patterns 2015, Tome 18 (2015-2016) no. 2.

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

We study the iteration of the process "a particle jumps to the right" in permutations. We prove that the set of permutations obtained in this model after a given number of iterations from the identity is a class of pattern avoiding permutations. We characterize the elements of the basis of this class and we enumerate these "forbidden minimal patterns" by giving their bivariate exponential generating function: we achieve this via a catalytic variable, the number of left-to-right maxima. We show that this generating function is a D-finite function satisfying a nice differential equation of order~2. We give some congruence properties for the coefficients of this generating function, and we show that their asymptotics involves a rather unusual algebraic exponent (the golden ratio $(1+\sqrt 5)/2$) and some unusual closed-form constants. We end by proving a limit law: a forbidden pattern of length $n$ has typically $(\ln n) /\sqrt{5}$ left-to-right maxima, with Gaussian fluctuations. 
@article{DMTCS_2016_18_2_a10,
     author = {Banderier, Cyril and Baril, Jean-Luc and Santos, C\'eline Moreira Dos},
     title = {Right-jumps and pattern avoiding permutations},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {18},
     number = {2},
     year = {2015-2016},
     doi = {10.46298/dmtcs.1344},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1344/}
}
TY  - JOUR
AU  - Banderier, Cyril
AU  - Baril, Jean-Luc
AU  - Santos, Céline Moreira Dos
TI  - Right-jumps and pattern avoiding permutations
JO  - Discrete mathematics & theoretical computer science
PY  - 2015-2016
VL  - 18
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1344/
DO  - 10.46298/dmtcs.1344
LA  - en
ID  - DMTCS_2016_18_2_a10
ER  - 
%0 Journal Article
%A Banderier, Cyril
%A Baril, Jean-Luc
%A Santos, Céline Moreira Dos
%T Right-jumps and pattern avoiding permutations
%J Discrete mathematics & theoretical computer science
%D 2015-2016
%V 18
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1344/
%R 10.46298/dmtcs.1344
%G en
%F DMTCS_2016_18_2_a10
Banderier, Cyril; Baril, Jean-Luc; Santos, Céline Moreira Dos. Right-jumps and pattern avoiding permutations. Discrete mathematics & theoretical computer science, Permutation Patterns 2015, Tome 18 (2015-2016) no. 2. doi : 10.46298/dmtcs.1344. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.1344/

Cité par Sources :