counting Eulerian circuits on complete directed graph

Question

I have a complete directed graph $G$ (including self-loops). How can I count the number of Eulerian circuits on $G$?

For example, in the simple case of $n=2$, there are clearly 4 Eulerian circuits. However, I'm not getting that result. I know that the number of Eulerian circuits $EC(G)$ can be calculated as $EC(G) = t(G) \times {\displaystyle \prod_{v \in V} (\text{deg}(v)-1)!}$.

Since each vertex has a degree of $n$ (in-degree = out-degree = $n$), I expect it to reduce to $EC(G) = t(G) \times ((n-1)!)^n$. Then, since the number of spanning trees $t(G)$ in a complete directed graph with $n$ vertices is $n^{n-1}$, we end up with $EC(G) = n^{n-1} \times (n-1)!^n$.

This gets 2 for $n=2$ instead of 4. What am I doing wrong?

Answer 1

First, note that you should have $n^{n-2}$ instead of $n^{n-1}$ since you are counting the number of rooted directed trees with a fixed root (equivalently, the number of unrooted undirected trees on $n$ nodes).

Next, the formula you have given only counts Eulerian circuits up to rotation. Thus, in the case of $n = 2$, the (corrected) formula $n^{n-2}(n-1)!^{n}$ only gives $1$ Eulerian circuit, and the $4$ circuits you have counted are all the same up to rotation.

If you are interested in the number of Eulerian circuits where the starting point is taken into account, then this would be $n^2 \cdot n^{n-2}(n-1)!^n = n!^n$. Indeed, this gives $4$ for $n = 2$.