Common intervals in permutations

Abstract : An interval of a permutation is a consecutive substring consisting of consecutive symbols. For example, 4536 is an interval in the permutation 71453682. These arise in genetic applications. For the applications, it makes sense to generalize so as to allow gaps of bounded size δ -1, both in the locations and the symbols. For example, 4527 has gaps bounded by 1 (since 3 and 6 are missing) and is therefore a δ -interval of 389415627 for δ =2. After analyzing the distribution of the number of intervals of a uniform random permutation, we study the number of 2-intervals. This is exponentially large, but tightly clustered around its mean. Perhaps surprisingly, the quenched and annealed means are the same. Our analysis is via a multivariate generating function enumerating pairs of potential 2-intervals by size and intersection size.\par
Keywords : permutations intervals
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2006, 8, pp.189-214
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 19 mars 2014 - 14:31:14
Dernière modification le : jeudi 11 janvier 2018 - 06:21:31
Document(s) archivé(s) le : jeudi 19 juin 2014 - 11:59:10


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00961109, version 1



Sylvie Corteel, Guy Louchard, Robin Pemantle. Common intervals in permutations. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2006, 8, pp.189-214. 〈hal-00961109〉



Consultations de la notice


Téléchargements de fichiers