Discrete Mathematics & Theoretical Computer Science |

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.

Source: arXiv.org:1512.02171

Volume: Vol. 18 no. 2, Permutation Patterns 2015

Section: Permutation Patterns

Published on: February 10, 2017

Accepted on: February 10, 2017

Submitted on: February 10, 2017

Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics,Mathematics - Probability

This page has been seen 559 times.

This article's PDF has been downloaded 472 times.