As our main result, we give a randomized fixed parameter tractable
algorithm to approximately count the number of copies of a
k-vertex graph with bounded treewidth in an n vertex graph. As a
consequence, we get randomized algorithms with running time
k^{O(k)}n^{O(1)}, approximation ratio 1/k^{O(k)}, and error
probability 2^{-n^{O(1)}} for the following problems:
\begin{itemize}
\item Approximately counting the number of matchings of size k in an
n vertex graph.
\item Approximately counting the number of paths of length k in an
n vertex graph.
\end{itemize}
Our algorithm is based on the Karp-Luby approximate counting technique
applied to fixed parameter tractable problems, and the color-coding
technique (based on perfect hashing) of Alon, Yuster and Zwick.

It is interesting to note in contrast that the \emph{exact} counting
versions of the above two problems are recently shown by Flum and
Grohe to be hard for the parameterized complexity class \W[1]. Hence
no exact counting algorithm with running time f(k) n^{b+O(1)} is
likely to exist these two problems, for any computable function f: {\cal N} \rightarrow {\cal N}.

We also show some \W-hardness results for parameterized exact
counting problems, whose decision versions are known to be fixed
parameter tractable. These problems include counting versions of
weight k satisfying assignment of a bounded DNF formula, and finding
a k-clique or a k-independent set in a graph.

We give a randomized approximation algorithm taking
O(k^{O(k)}n^{b+O(1)}) time to count the number of copies of a
k-vertex graph with treewidth at most b in an n vertex graph
G with approximation ratio 1/k^{O(k)} and error probability
inverse exponential in n. This algorithm is based on the
Karp-Luby approximate counting technique applied to
fixed parameter tractable problems, and the color-coding
technique (based on perfect hashing) of Alon, Yuster and Zwick. As a
consequence we get a randomized fixed parameter tractable algorithm
to approximately count the number of matchings of size k or paths
of length k in a given graph.
We also give some results (both W-hardness and fixed parameter
tractability) on the exact counting versions of some of these and
other fixed parameter tractable problems. These problems include
counting versions of k-vertex cover, weight k satisfying
assignment of a bounded DNF formula, and finding a k-clique or a
k-independent set in a graph.