Counting occurrences for a finite set of words: an inclusion-exclusion approach - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

Counting occurrences for a finite set of words: an inclusion-exclusion approach

Résumé

In this paper, we give the multivariate generating function counting texts according to their length and to the number of occurrences of words from a finite set. The application of the inclusion-exclusion principle to word counting due to Goulden and Jackson (1979, 1983) is used to derive the result. Unlike some other techniques which suppose that the set of words is reduced (i.e., where no two words are factor of one another), the finite set can be chosen arbitrarily. Noonan and Zeilberger (1999) already provided a M APLE package treating the non-reduced case, without giving an expression of the generating function or a detailed proof. We give a complete proof validating the use of the inclusion- exclusion principle and compare the complexity of the method proposed here with the one using automata for solving the problem.
Fichier principal
Vignette du fichier
aofa07.pdf (178.3 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00452702 , version 1 (02-02-2010)
hal-00452702 , version 2 (17-08-2015)

Identifiants

  • HAL Id : hal-00452702 , version 1

Citer

Frédérique Bassino, Julien Clément, Julien Fayolle, Pierre Nicodème. Counting occurrences for a finite set of words: an inclusion-exclusion approach. AofA'07, Jun 2007, Juan les Pins, France. pp.29-44. ⟨hal-00452702v1⟩
1091 Consultations
742 Téléchargements

Partager

Gmail Facebook X LinkedIn More