Chapter 9 - Counting, Coding, and Sampling with Words

Summary

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:

1. (i) Counting: determine for all n ≥ 0, the cardinal Card (C_n) of the set C_n of objects with size n.

2. (ii) Sampling: design an algorithm RandC that, for any n, produces a random object uniformly chosen in C_n: in other terms, the algorithm must satisfy P(RandC(n) = O) = 1/Card (C_n) for any object O ∊ C_n.

3. (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₂ 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.