  Bulatov (2008) gave a dichotomy for the counting constraint satisfaction
problem #CSP. A problem from #CSP is characterised by a constraint language,
which is a fixed, finite set of relations over a finite domain D. An instance
of the problem uses these relations to constrain the variables in a larger set.
Bulatov showed that the problem of counting the satisfying assignments of
instances of any problem from #CSP is either in polynomial time (FP) or is
#P-complete. His proof draws heavily on techniques from universal algebra and
cannot be understood without a secure grasp of that field. We give an
elementary proof of Bulatov's dichotomy, based on succinct representations,
which we call frames, of a class of highly structured relations, which we call
strongly rectangular. We show that these are precisely the relations which are
invariant under a Mal'tsev polymorphism. En route, we give a simplification of
a decision algorithm for strongly rectangular constraint languages, due to
Bulatov and Dalmau (2006). We establish a new criterion for the #CSP dichotomy,
which we call strong balance, and we prove that this property is decidable. In
fact, we establish membership in NP. Thus, we show that the dichotomy is
effective, resolving the most important open question concerning the #CSP
dichotomy.
