Counting, Coding, and Sampling with Words
M. Lothaire · Cambridge University Press eBooks · 2005
Introduction This chapter illustrates the use of words to derive enumeration results and algorithms for sampling and coding. Given a family C of combinatorial structures, endowed with a size such that the subset C n of objects of size n is finite, we consider three problems: (i) Counting : determine for all n ≥ 0, the cardinal Card ( C n ) of the set C n of objects with size n . (ii) Sampling : design an algorithm R and C that, for any n , produces a random object uniformly chosen in C n : in other terms, the algorithm must satisfy P (R and C ( n ) = O ) = 1/Card ( C n ) for any object O ∊ C n . (iii) Optimal coding : construct a function φ that maps injectively objects of C on words of {0, 1}* in such a way that an object O of size n is coded by a word φ( O ) of length roughly bounded above by log 2 Card ( C n ). These three problems have in common an enumerative flavour, in the sense that they are immediately solved if a list of all objects of size n is available. However, since in general there is an exponential number of objects of size n in the families in which we are interested, this solution is in no way satisfying. For a wide class of so-called decomposable combinatorial structures, including nonambiguous algebraic languages, algorithms with polynomial complexity can be derived from the rather systematic recursive method. Our aim is to explore classes of structures for which an even tighter link exists between counting, sampling, and coding.