Proving $\#CYCLE \in \#P$
The class #P consists of those functions $f$ such that there is a polytime relation $R$ and a polynomial bound $p$ satisfying
$$
 f(x) = |\{ |y| &lt; p(|x|) : R(x,y) \}|.
$$
In words, if we think of $y$ as a "witness" for $x$, then $f(x)$ should count the number of witnesses for $x$. For example, if $R(x,y)$ is the relation that $y$ is a cycle in the graph $x$, then (if you're careful enough) $f(x)$ will count the number of cycles in the graph $x$. You need to be a bit careful to count each cycle exactly once.