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

1 Answer 1

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

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.