Right-jumps and pattern avoiding permutations
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2017-02-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/1344/pdf |
| _version_ | 1797270097304223744 |
|---|---|
| author | Cyril Banderier Jean-Luc Baril Céline Moreira Dos Santos |
| author_facet | Cyril Banderier Jean-Luc Baril Céline Moreira Dos Santos |
| author_sort | Cyril Banderier |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:58:51Z |
| format | Article |
| id | doaj.art-bab87146066d4c41a4c6c42eed68e5ce |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:51Z |
| publishDate | 2017-02-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-bab87146066d4c41a4c6c42eed68e5ce2024-03-07T15:30:38ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502017-02-01Vol. 18 no. 2, Permutation...Permutation Patterns10.46298/dmtcs.13441344Right-jumps and pattern avoiding permutationsCyril BanderierJean-Luc BarilCéline Moreira Dos SantosWe 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.https://dmtcs.episciences.org/1344/pdfcomputer science - discrete mathematicsmathematics - combinatoricsmathematics - probability |
| spellingShingle | Cyril Banderier Jean-Luc Baril Céline Moreira Dos Santos Right-jumps and pattern avoiding permutations Discrete Mathematics & Theoretical Computer Science computer science - discrete mathematics mathematics - combinatorics mathematics - probability |
| title | Right-jumps and pattern avoiding permutations |
| title_full | Right-jumps and pattern avoiding permutations |
| title_fullStr | Right-jumps and pattern avoiding permutations |
| title_full_unstemmed | Right-jumps and pattern avoiding permutations |
| title_short | Right-jumps and pattern avoiding permutations |
| title_sort | right jumps and pattern avoiding permutations |
| topic | computer science - discrete mathematics mathematics - combinatorics mathematics - probability |
| url | https://dmtcs.episciences.org/1344/pdf |
| work_keys_str_mv | AT cyrilbanderier rightjumpsandpatternavoidingpermutations AT jeanlucbaril rightjumpsandpatternavoidingpermutations AT celinemoreiradossantos rightjumpsandpatternavoidingpermutations |