Some Families of Trees Arising in Permutation Analysis
| Autor: | Mathilde Bouvel, Cyril Nicaud, Marni Mishna |
|---|---|
| Přispěvatelé: | University of Zurich, Designing the Future of Computational Models (MOCQUA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Department of Mathematics, Laboratoire d'Informatique Gaspard-Monge (LIGM), École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Université Gustave Eiffel, This work was partially supported by ANR project Magnum (2010-BLAN-0204), NSERC Discovery grant 31-611453, and funding by Université Paris-Est., ANR-10-BLAN-0204,MAGNUM,Méthodes Algorithmiques de Génération aléatoire Non Uniforme, Modèles et applications.(2010) |
| Rok vydání: | 2020 |
| Předmět: |
simple varieties of trees
340 Law 610 Medicine & health Arity Interval tree Prime (order theory) Theoretical Computer Science Combinatorics Permutation 510 Mathematics 2604 Applied Mathematics tree parameters FOS: Mathematics Filtration (mathematics) Mathematics - Combinatorics Discrete Mathematics and Combinatorics [INFO]Computer Science [cs] Limit (mathematics) [MATH]Mathematics [math] 2614 Theoretical Computer Science Mathematics Series (mathematics) Applied Mathematics Permutations random generation asymptotic formulas 10123 Institute of Mathematics 05A16 Computational Theory and Mathematics 2607 Discrete Mathematics and Combinatorics 2608 Geometry and Topology Combinatorics (math.CO) Geometry and Topology Tree (set theory) 1703 Computational Theory and Mathematics |
| Zdroj: | The Electronic Journal of Combinatorics The Electronic Journal of Combinatorics, Open Journal Systems, 2020, ⟨10.37236/6504⟩ The Electronic Journal of Combinatorics, 2020, ⟨10.37236/6504⟩ |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/6504 |
| Popis: | We extend classical results on simple varieties of trees (asymptotic enumeration, average behavior of tree parameters) to trees counted by their number of leaves. Motivated by genome comparison of related species, we then apply these results to strong interval trees with a restriction on the arity of prime nodes. Doing so, we describe a filtration of the set of permutations based on their strong interval trees. This filtration is also studied from a purely analytical point of view, thus illustrating the convergence of analytic series towards a non-analytic limit at the level of the asymptotic behavior of their coefficients. 26 pages; An extended abstract of this work appeared in the Proceedings of the International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC) 2013 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|