There are some counting problems which involve counting exponentially many things (relative to the size of the input), and yet have surprising polynomial-time exact, deterministic algorithms. Examples include:
- Counting perfect matchings in a planar graph (the FKT algorithm), which is the basis for how holographic algorithms work.
- Counting spanning trees in a graph (via Kirchhoff's matrix tree theorem).
A key step in both of these examples is reducing the counting problem to computing the determinant of a certain matrix. A determinant is itself, of course, a sum of exponentially many things, yet can surprisingly be computed in polynomial time.
My question is: are there any "surprisingly efficient" exact and deterministic algorithms known for counting problems which do not reduce to computing a determinant?