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.