Is there a theorem which relates calculating the total number of a combinatorial object with picking one at random?
These are known as ranking and unranking functions.  You are right about the correspondence between recurrence relations for counting and unranking algorithms.