Some simple varieties of trees arising in permutation analysis

Résumé : Nous commençons par étendre les résultats classiques sur les variétés simples d'arbres aux arbres comptés selon leur nombre de feuilles, puis nous décrivons une filtration de l'ensemble des permutations qui repose sur leurs arbres des intervalles communs. Pour toute sous-classe, nous donnons des formules asymptotiques pour le nombre d'arbres (comptés selon les feuilles), le nombre moyen de nœuds d'arité fixée, la moyenne de la somme des tailles des sous-arbres, et le nombre moyen de nœuds internes. Cette filtration est motivée par des problématiques de comparaison de génomes.
Type de document :
Communication dans un congrès
Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.825-836, 2013, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01229665
Contributeur : Alain Monteil <>
Soumis le : mardi 17 novembre 2015 - 10:19:34
Dernière modification le : mercredi 11 avril 2018 - 12:12:03
Document(s) archivé(s) le : jeudi 18 février 2016 - 11:33:28

Fichier

dmAS0170.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01229665, version 1

Citation

Mathilde Bouvel, Marni Mishna, Cyril Nicaud. Some simple varieties of trees arising in permutation analysis. Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.825-836, 2013, DMTCS Proceedings. 〈hal-01229665〉

Partager

Métriques

Consultations de la notice

204

Téléchargements de fichiers

181