Lesson 1

Suppose there are \(k\) combinatorial objects (sets, permutations, bracket sequences) numbered from \(0\) to \(k-1\). Can we efficiently (without enumerating all these objects) determine the index of a given object and the object with a given index? In this section we will learn to answer such questions efficiently. This is useful, for example, in the following situations.

• This allows compact encoding (and transmission, if needed) of objects. For example, if you need to compute a certain characteristic of each bracket sequence, you can store it in an array rather than a hash table.


• This makes the process of generating a random object simple and transparent: generate a random index and reconstruct the object.