Is there a theorem which relates calculating the total number of a combinatorial object with picking one at random?

Question

A common algorithmic challenge is to generate an object of a certain kind, uniformly at random. For example, generating a random permutation of size $k$ from a given (multi)set of $N$ characters, as in this question.

I've noticed that when solving such tasks, any algorithm for calculating the number of such combinatorial objects via a recurrence relation can be transformed into an algorithm to generate such combinatorial objects. My question is, is there a name for this technique? Is there a theorem which says when this is true?

For example, suppose I want to generate a random sequence of $n$ $1$s and $0$s, where there are no two adjacent $1$s. I can begin by letting $a[n]$ be the number of such sequences, and observe that $$ a[n] = a[n-1] + a[n-2]. $$

(This is the Fibonacci relation.) This allows me to efficiently calculate a table of $a[i]$ for $i = 1$ to $i = n$. Now if I want to generate a random such sequence, all I have to do is:

Step 1: Generate a random value $r$ from $1$ to $a[n]$.

Step 2: Use the recurrence relation to locate a sub-term which corresponds to the $r$th sequence:

• If $r \le a[n-1]$, recursively find the $r$th sequence counted by $a[n-1]$, and append a $0$.

• Otherwise, if $a[n-1] < r \le a[n-1] + a[n-2]$, set $r' = r - a[n-1]$, and recursively find the $r'$th sequence counted by $a[n-2]$, and append a $01$.

What seems to be going on here is that, given any recurrence relation for $a[n]$, I can transform this into a recursive algorithm which returns the $r$th object counted by $a[n]$. I'm assuming this is well-known, so I would be interested in any references or classic results about this. In particular, this isn't just specific to the example $a[n]$, but should be true for any recurrence relation satisfying certain properties.

Also, I think this may be related to some research on random testing.

Answer 1

These are known as ranking and unranking functions. You are right about the correspondence between recurrence relations for counting and unranking algorithms.