In the theory of complexity,
- the counting problem is to compute the number of specified structures, e.g., count the triangles in a given graph.
- the sampling problem concerns how to generate uniformly an instance with the specified structures, e.g., generate at random a triangle from a given graph and each triangle is to appear with equal probability.
People usually believe that the sampling problem is no more difficult (in the sense of complexity) than the counting problem. Especially, when the combinatorial structure is self-reducible, the approximate sampling and approximate counting problems are equivalent, i.e., every randomized fully polynomial approximation scheme (FPRAS) can be converted into a fully polynomial-time approximate sampler, and vice versa.
I'm instead interested in the exact counting and sampling problems, and wonder in this case, if the sampling problem is always difficult than counting. In particular, I want to ask if there is a counterexample for which counting is easier than sampling?