In Peter J. Cameron's book "Permutation Groups" I found the following quote



> 
> It is a slogan of modern enumeration theory that the ability to count a set is closely related to the ability to pick a random element from that set (with all elements equally likely).
> 
> 
> 


Indeed, one can count and sample uniformly from labeled trees, spanning trees, spanning forests, dimer models, young tableaux, plane partitions etc. However one can't do either of these very efficiently with groups, for example. My question is if one can make this into a rigorous statement, perhaps through complexity theory. That is, if I have an algorithm to produce a uniform sample from a set of objects, can I somehow come up with an efficient way to count them or vice-versa? 


Does this slogan have a standard name? Are there any references?



Enumeration and random selection
Yes, there is formal way of saying this using complexity theory. I think the statement is something like: For all self-reducible relations, the problems of approximate sampling and approximate counting are equivalent (with polynomial time reductions). More specifically, for such problems, the existence of an FPRAS (fully polynomial-time randomized approximation scheme) implies the existence of an FPAUS (fully polynomial-time almost uniform sampler) and vice versa.


References:


* Jerrum, Valiant, and Vazirani, "Random generation of combinatorial structures from a uniform distribution"
* Sinclair and Jerrum, "Approximate counting, uniform generation and rapidly mixing Markov chains"


Alternately, just search for "approximate counting", "approximate sampling" and "self-reducible" on google, and you'll find lots of lecture notes and presentations explaining the ideas.


