Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Right-jumps and patt ...
Article

Right-jumps and pattern avoiding permutations

Cyril Banderier, Jean-Luc Baril, Céline Moreira Dos Santos
Download article
Open on arXiv
Imported on
February 10, 2017
Published on
February 10, 2017
Last modified on
March 31, 2025
Special issue 18
vol. 18:2, Permutation Patterns 2015
Permutation Patterns
DOI
10.46298/dmtcs.1344
License
arXiv.org - Non-exclusive license to distribute
Indicators
1085
Views
959
Downloads

Right-jumps and pattern avoiding permutations

Cyril Banderier, Jean-Luc Baril, Céline Moreira Dos Santos
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+\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
Keywords
  • Computer Science - Discrete Mathematics
  • Mathematics - Combinatorics
  • Mathematics - Probability
Preview
Loading PDF preview...