Surprising algorithms for counting problems 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?
I don't know if the following problems reduce or not to computing the determinant, but I will list anyway:

1) Counting the number of paths in a DAG from a node $v_0$ to a node $v_f$. 
But this is not surprising. Simply determining whether $v_f$ is reachable from $v_0$ is in NL, and thus in DET. I have no idea about the counting version.

2) Counting the number of solutions of problems definable in MSO-logic in structures of bounded Tree width.  See for example the paper which buids on works of Courcelle, Arnborg and others.

3) If you have a function $f:\{0,1\}^{n}\rightarrow \{0,1\}$, that can be expressed by a bolean circuit of logarithmic tree width, than you can 
count the number of inputs $x$ such that $f(x)=1$ by devising a quantum 
circuit $U_f$ which sends $|x\rangle|0\rangle$ to $|x\rangle|f(x)\rangle$, 
and classically simulating the probability of measuring $|1\rangle$ in the 
second register after the application of $U_fH^{\otimes n}|0\rangle|0\rangle$ using these results.