Find a closed formula for the number of Euler circuits on a complete (undirected) graph of n nodes.

This was posed as a "research problem" in Oystein Ore's book "Theory of
Graphs" (1960), but to my knowledge has never been solved.  It is
possible to write down a set of linear equations for the answer, but
the number of equations ( something like 2^((n-1)*(n-2)/2) ) doesn't
inspire much confidence.

In fact, I'm not even aware that the asymptotic answer is known.  An
equivalent problem is the following:  Take an n-vertex complete graph
(n odd).  Start at the first vertex and walk at random along the edges
of the graph, without using any edge more than once.  As you arrive at
each vertex, you must choose at random one of the incident edges that
have not been used before.  Sooner or later you will get stuck.  (A
simple parity argument shows that you can only get stuck at the
starting vertex.)  What is the probability that you only get stuck
after traversing every edge of the graph?  Experimental evidence
suggests that the probability is roughly proportional to 1/sqrt(n).
Proof, anyone?

Values for the number of Euler circuits up to 17 vertices appear in
B. D. McKay, Applications of a technique for labelled enumeration,
Congressus Numerantium 40 (1983) 207-221.  This part of the paper was
joint work with R. W. Robinson.  The value for n=17 has 107 digits.

-- Brendan McKay <bdm@anucsd.oz>, Australian National University

There is some ambiguity here.  Does where we start matter?  (Is (123)
different from (231)?)  Does reversing the direction matter?  (Is (123)
different from (132)?)  Does relabelling the vertices matter?  (Is
(1234513524) different from (1235413425)?)

Assuming that starting point and direction matter, but relabelling does
not, I got 1 for n=3, and 22 for n=5.  (Note that Lambert posted some
numbers assuming that starting point and direction do not matter, but
relabelling does.)

-- Frank Adams <franka@mmintl.UUCP>

In article <2318@mmintl.UUCP> franka@mmintl.UUCP (Frank Adams) writes:
) In article <50@piring.cwi.nl> lambert@cwi.nl (Lambert Meertens) writes:
) >It can also happen that the walk can be completed but that some edges
) >have been traversed twice (in opposite direction) and some others not
) >at all.
) No, the forbidden choices from a vertex include those by which the
) vertex has been entered, as well as those from which it has been
) exited.

That is correct; my mistake.

Just for the record, I looked at the article by Brendan McKay, and the
results there confirm those of my brute-force enumeration:

    3:        1
    5:      132 = 2^2 * 3 * 11
    7: 64988160 = 2^10 * 3 * 5 * 4231

(numbers modulo start point and direction of traversal).
The two following cases are

    9: 455760028510617600 = 2**15 * 3**11 * 5**2 * 7 * 11 * 40787
   11: 128663499619046483713892580065280 =
                        2**40 * 3**13 * 5 * 7 * 23 * 643 * 141798739

-- Lambert Meertens <lambert@cwi.nl>, CWI, Amsterdam