Right-jumps and pattern avoiding permutations

zbMATH Open1400.05005arXiv1512.02171MaRDI QIDQ4557005FDOQ4557005

Jean-Luc Baril, Cyril Banderier, Céline Moreira Dos Santos

Publication date: 28 November 2018

Abstract: 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+sqrt5)/2$) and some unusual closed-form constants. We end by proving a limit law: a forbidden pattern of length $n$ has typically $(lnn)/sqrt5$ left-to-right maxima, with Gaussian fluctuations.

Full work available at URL: https://arxiv.org/abs/1512.02171

zbMATH Keywords

generating functionanalytic combinatoricsD-finite functionpermutation patternsupercongruenceinsertion sortleft-to-right maximum

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Cited In (3)

• The operators \(F_i\) on permutations, 132-avoiding permutations and inversions
• On the period mod $m$ of polynomially-recursive sequences: a case study
• Title not available (Why is that?)

This page was built for publication: Right-jumps and pattern avoiding permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4557005)