q-Enumeration of words by their total variation

Ligia Loreta Cristea 1 Helmut Prodinger 2
1 Institut fur Mathematik
2 DMS - Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]
Abstract : In recent work, Mansour [Discrete Math. Theoret. Computer Science 11, 2009, 173--186] considers the problem of enumerating all words of length n over {1,2,...,k} (where k is a given integer), that have the total variation equal to a given integer m. In the present paper we study various types of random words over the infinite alphabet ℕ, where the letters have geometric probabilities. We are interested in the probabilities of words of given type to have a given total variation.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity, 12 (3), pp.139-150
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-00993529
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 20 mai 2014 - 14:29:35
Dernière modification le : mercredi 29 novembre 2017 - 10:26:22
Document(s) archivé(s) le : mercredi 20 août 2014 - 11:36:23

Fichier

1475-5654-1-PB.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00993529, version 1

Collections

TDS-MACS

Citation

Ligia Loreta Cristea, Helmut Prodinger. q-Enumeration of words by their total variation. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity, 12 (3), pp.139-150. 〈hal-00993529〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

155

Téléchargements de fichiers

269

Contact


archive-ouverte@inria.fr