Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
1  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.