# 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.

-

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.

-
The result is correct. You’ve double-counted: there are only $\binom52\cdot2^2$ permutations of $[6]$ that are products of two $3$-cycles, because there are $\binom52$ ways to fill out the $3$-cycle containing $1$. See this question and my answer. – Brian M. Scott Oct 25 '13 at 9:20

We can solve this one using species which possibly qualifies as a combinatorial proof.

First, observe that 2-regular graphs are sets of undirected cycles, which is the species $$\mathfrak{P}( \mathfrak{D}_{=3}(\mathcal{Z}) + \mathfrak{D}_{=4}(\mathcal{Z}) + \mathfrak{D}_{=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 species $$\mathfrak{P}( \mathfrak{C}_{=3}(\mathcal{Z}) + \mathfrak{C}_{=4}(\mathcal{Z}) + \mathfrak{C}_{=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.

-