Cyril Banderier ; Jean-Luc Baril ; Céline Moreira Dos Santos - Right-jumps and pattern avoiding permutations

dmtcs:1344 - Discrete Mathematics & Theoretical Computer Science, February 10, 2017, Vol. 18 no. 2, Permutation Patterns 2015 - https://doi.org/10.46298/dmtcs.1344
Right-jumps and pattern avoiding permutationsArticle

Authors: Cyril Banderier ; Jean-Luc Baril ; Céline Moreira Dos Santos

    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.

    Comment: Following the work presented at the conferences Analysis of Algorithms (AofA'15) and Permutation Patterns'15, this arXiv version corresponds to the version published in DMTCS, up to minor details/typos fixed here


    Volume: Vol. 18 no. 2, Permutation Patterns 2015
    Section: Permutation Patterns
    Published on: February 10, 2017
    Imported on: February 10, 2017
    Keywords: Computer Science - Discrete Mathematics, Mathematics - Combinatorics, Mathematics - Probability

    Consultation statistics

    This page has been seen 794 times.
    This article's PDF has been downloaded 715 times.