Let $X=\{(i,j); i,j=1, \dots, n, i \neq j\}$ be the set of pairs. How do you count the subsets $L$ of $X$ that satisfy this property: for every $k=1,\dots, n$ there are as many elements of $L$ with first coordinate $k$ as with second coordinate equal to $k$?

Here's an example. For n=3, the subset {(1,2),(2,3),(3,1)} satisfies this property. Same as with {(1,3),(3,1)}, and so on. I think there are 9 such L, including the empty set for this case.

  • $\begingroup$ i can't offer much help, but one approach might be to label n nodes and represent the coordinates as vectors on a directed graph $\endgroup$ – user398748 Jul 14 '18 at 23:42
  • $\begingroup$ I count $10$ for $n=3$: $2^3=8$ possibilities with each of the three two-cycles either there or not, and two different orientations for a three-cycle. $\endgroup$ – joriki Jul 15 '18 at 7:44

This is OEIS sequence A007080. If you take $\{1,\ldots\,n\}$ as the set of vertices of a directed graph, and the pairs as directed edges, the subsets you want correspond to directed graphs in which indegree and outdegree coincide for every vertex. Alternatively, you could describe this as the flows without sinks or sources on a complete digraph with $n$ vertices that use each edge at most once.

There are apparently two different definitions of a “Eulerian digraph”. One definition requires a path to exist that visits all edges exactly once. This is equivalent to the indegrees and outdegrees being equal and the edges being connected. There is also another definition, used e.g. in this article, that doesn't require connectedness and defines Eulerian digraphs directly via the equality of indegrees and outdegrees. It appears that this is the definition implied in the OEIS entry, as the count there coincides up to $n=4$ with my count by hand, and for $n=4$ there are $3$ disconnected graphs that would change the result if the other definition were being used.

The OEIS entry contains an asymptotic formula,

$$ a_n\sim\mathrm e^{-\frac14}\sqrt n\left(\frac{2^n}{\sqrt{\pi n}}\right)^{n-1} \;, $$

and some links, but not much else. Generally OEIS tends to be good at collecting knowledge about such sequences, so it's likely that not much more is known and it will not be easy to find out much more.

This paper improves on the asymptotic result:

$$ a_n=\mathrm e^{-\frac14}\sqrt n\left(\frac{2^n}{\sqrt{\pi n}}\right)^{n-1}\left(1+\frac3{16n}+O\left(\frac1{n^2}\right)\right) \;. $$

It also describes a method for obtaining higher-order corrections.

  • $\begingroup$ P.S.: This OEIS entry on Eulerian digraphs explicitly states that it includes disconnected graphs (which supports my interpretation that the other one does). $\endgroup$ – joriki Jul 15 '18 at 8:38
  • 1
    $\begingroup$ Wow, thank you very much for this help. No surprise I was not able to figure out a closed formula then - I am at peace now :). $\endgroup$ – Camilo Jul 16 '18 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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