On a formula that relates 2-regular graphs on $n$ vertices and permutations of $n$ elements with no fixed points or cycles of length 2 Let $g_n=$ number of 2-regular graphs on $n$ vertices
Let $c_n=$ permutations of $n$ with no fixed points or cycles of length 2
By a computation with the exponential generating function I think that the following formula should be true:
$$c_n=\sum_{k=0}^n\binom{n}{k}g_kg_{n-k}\;.$$ There is a combinatorial proof of this fact?
The only thing that I noticed is that permutations that are cycles correspond to 2-regular connected graphs 2-to-1.
 A: There seems to be a double-counting error in your result.
First off, it appears that by the number of $2$-regular graphs you mean what one would more precisely call the number of $2$-regular labeled graphs, whereas I believe the more usual interpretation of that phrase would be the number of $2$-regular unlabeled graphs, that is, the number of isomorphism classes of $2$-regular graphs.
The first interesting case is $n=6$. In this case, in addition to the $120$ $6$-cycles corresponding to $60$ cycle graphs, which your result gets right, there are some permutations and graphs that have two $3$-cycles. In both cases there are $\binom63$ ways to select the two groups of three that make up the cycles. In the case of the graphs, this completely determines the graph, so there are $\binom63$ such graphs. In the case of the permutations, there are two ways to orient the cycle for each cycle, for a total of four ways of orienting the two cycles, so there are $4\binom63$ such permutations. However, you result contains only one contribution in addition to the $2\binom63$ coming from $g_0g_6$ and $g_6g_0$, and that's $\binom63g_3g_3$, which is $\binom63$, so the result is one $\binom63$ short.
A: We  can solve this  one using combinatorial classes which  possibly qualifies  as a combinatorial proof.

First, observe  that 2-regular graphs  are sets of  undirected cycles,
which is the class
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\textsc{SET}(
\textsc{DHD}_{=3}(\mathcal{Z})
+ \textsc{DHD}_{=4}(\mathcal{Z})
+ \textsc{DHD}_{=5}(\mathcal{Z})
+ \cdots).$$
This gives the generating function
$$G(z) = \exp
\left(\frac{1}{2} \frac{z^3}{3}
+ \frac{1}{2} \frac{z^4}{4}
+ \frac{1}{2} \frac{z^5}{5}
+ \frac{1}{2} \frac{z^6}{6}
+ \cdots\right),$$
which is
$$G(z) = 
\exp\left(-\frac{z}{2}-\frac{z^2}{4}\right)
\frac{1}{\sqrt{1-z}}.$$
On the other hand, permutations with no fixed points or
2-cycles are the class
$$\textsc{SET}(
\textsc{CYC}_{=3}(\mathcal{Z})
+ \textsc{CYC}_{=4}(\mathcal{Z})
+ \textsc{CYC}_{=5}(\mathcal{Z})
+ \cdots)$$
which gives the generating function
$$C(z) = \exp
\left(\frac{z^3}{3}
+ \frac{z^4}{4}
+ \frac{z^5}{5}
+ \frac{z^6}{6}
+ \cdots\right),$$
which is
$$C(z) = 
\exp\left(-\frac{z}{1}-\frac{z^2}{2}\right)
\frac{1}{1-z}.$$
Observe that when we  multiply two exponential generating functions of
the sequences $\{a_n\}$ and $\{b_n\}$ we get that
$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} 
\sum_{n\ge 0} b_n \frac{z^n}{n!}
= \sum_{n\ge 0} 
\sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\
= \sum_{n\ge 0} 
\sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!}
= \sum_{n\ge 0} 
\left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$
i.e. the  product of  the two generating  functions is  the generating
function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$
In the present case  we clearly have $A(z) = B(z) =  G(z)$ and we need
to prove that their convolution is $C(z).$

Note however that
$$G(z)^2 = \left(\exp\left(-\frac{z}{2}-\frac{z^2}{4}\right)\right)^2
\frac{1}{\sqrt{1-z}^2}$$
which is
$$\exp\left(-\frac{z}{1}-\frac{z^2}{2}\right)
\frac{1}{1-z},$$
i.e. precisely $C(z),$ QED.
Here  we have  used the  fact that  the dihedral  group acting  on $q$
elements  contains   $2q$  permutations  and  the   cyclic  group  $q$
permutations.
