3
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ This smells a lot like a homework exercise to me. Hint: write the presentation participants in a 3xn table. Gerhard "If It Is, Please Cite" Paseman, 2012.11.06 $\endgroup$ Nov 6, 2012 at 20:34
  • $\begingroup$ The unlabeled version is more interesting, but it is not clear that is what you are asking. Gerhard "Ask Me About System Design" Paseman, 2012.11.06 $\endgroup$ Nov 6, 2012 at 20:35
  • $\begingroup$ No it isn't homework, sorry but wouldn't this be clear to you if you bothered reading the background I gave? $\endgroup$ Nov 6, 2012 at 21:42
  • $\begingroup$ I did read the background you gave. It is well crafted and might even be true. If I had to give motivation for homework, while disgusing it, what you gave is just the sort of example I would make up. Thus my response. Did you make use of the hint, and can you tell me if you mean the labeled or unlabeled version, or both? Gerhard "Didn't Say It Was Homework" Paseman, 2012.11.06 $\endgroup$ Nov 7, 2012 at 2:10
  • 1
    $\begingroup$ If you allow each student to be his own assistant once (but not twice), then you would be counting $n\times n$ matrices $M$ of 0's and 1's such that every row and column sum is two. If $f(n)$ is the number of such matrices, then $\sum f(n)x^n/n!^2 = (1-x)^{-1/2} e^{-x/2}$. See Enumerative Combinatorics, vol. 2, Cor. 5.5.11. Your problem introduces the extra requirement that $\mathrm{trace}(M)=0$, which makes things much more difficult, but conceivably the technique in the above reference can still be used. It looks to me that some variant of the ménage problem will be relevant. $\endgroup$ Nov 8, 2012 at 19:51

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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