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

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.