How to count 2-2 regular directed graphs with n vertices?

Question

A little bit of background:

In a small course a friend of mine is attending, everybody shall give a presentation about some topic. Now for each presentation, here can be two assistants which are other students that inform themselves about the topic and help moderating the discussion etc.

Of course, optimally, each participant gets two assistants for his presentation, and does assist in two others.

Surely, our combinatorics sense awoke and we wondered "How many possibilities are there of arranging studends, assistants and presentations together in the fair way?" ;)

The model:

An idea of modeling the situation was the following:

Let each student be represented by a vertex in a directed graph $G$. Then we draw an arc from $a$ to $b$ iff $a$ is assisting in $b$'s presentation.

Now the course situation in $G$ is fair if any vertex has two arcs going out and two coming in. In other words, $G$ is 2-2-regular. Thus, our problem comes down to

The Question

How manys 2-2 regular directed graphs are there on $n$ vertices?

If we call this number $R_n$, we had tried a recursive approach. Introduce a new vertex to an existing regular graph, then it needs two arcs that have to be removed elsewhere. We can have $\binom n 2$ possibilities of vertices to take them away, and 2 vertices each, so we'd get

$$ R_{n+1} = 4 \binom n 2 R_n $$

Of course this is wrong, we generate degenerate possibilities with this approach that we need to exclude, and that's where we run into problems.

So, any ideas on counting these 2-2-regular graphs, please?

Answer 1

Here is how it can be done. Probably the answer appears somewhere already, but I don't recall it and I'm too lazy to search.

Draw $2n$ dots $A=\lbrace a_1,a'_1,\ldots,a_n,a'_n\rbrace$ and another $2n$ dots $B=\lbrace b_1,b'_1,\ldots,b_n,b'_n\rbrace$. Take a matching from $A$ to $B$. Now make a graph with vertices $v_1,\ldots,v_n$ where there is an arc from $v_i$ to $v_j$ for every match between $\lbrace a_i,a'_i\rbrace$ and $\lbrace b_i,b'_i\rbrace$.

This has the 2-in, 2-out property but it might not be simple. That is (contrary to your application) it might have an arc from $v_i$ to itself (a loop), and it might have two arcs from $v_i$ to $v_j$ (a double edge). On the other hand, each labelled simple digraph appears for exactly $4^n$ matchings. So the number of digraphs is $P\times(2n)! \times 4^{-n}$, where $P$ is the probability that a random matching gives a simple digraph.

The bad events of having a loop or a double edge all involve distinct vertices except for double loops, so it is very easy to write down an inclusion-exclusion formula for $P$ as a triple summation over the number of single loops, double loops, and double edges. One or two of the summations might be possible explicitly but I'll be surprised if there is a closed form answer.

The same method yields the asymptotics easily. I think $P\sim e^{-5/2}$ but I might have miscalculated.