6533b7ddfe1ef96bd127544d
RESEARCH PRODUCT
Right-jumps and pattern avoiding permutations
Jean-luc BarilCéline Moreira Dos SantosCyril Banderiersubject
FOS: Computer and information sciencesD-finite function[ MATH.MATH-CV ] Mathematics [math]/Complex Variables [math.CV]Discrete Mathematics (cs.DM)General Computer Scienceinsertion sort[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM][ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO]left-to-right maximumPermutation patternTheoretical Computer Science[ MATH.MATH-NT ] Mathematics [math]/Number Theory [math.NT]Combinatorics[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]FOS: Mathematicsanalytic combinatoricsMathematics - CombinatoricsDiscrete Mathematics and CombinatoricsGolden ratioMathematicsProbability (math.PR)Generating function[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM][MATH.MATH-CV]Mathematics [math]/Complex Variables [math.CV]Function (mathematics)[MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT]Exponential function[MATH.MATH-PR]Mathematics [math]/Probability [math.PR]generating functionPermutation patternExponentAnalytic combinatoricssupercongruenceCombinatorics (math.CO)Maxima[ MATH.MATH-PR ] Mathematics [math]/Probability [math.PR]Mathematics - ProbabilityComputer Science - Discrete Mathematicsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2015-12-08 |