Let X=set of all pairs {(i,j)} with $i \neq j$. Counting subsets L of X that have equal number of pairs starting with k as pairs ending with k

Question

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.

Answer 1

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.