login
Number of Eulerian circuits on the complete graph K_{2n+1}, divided by (n-1)!^(2n+1).
(Formerly M2183)
10

%I M2183 #44 Oct 19 2022 11:24:45

%S 2,264,1015440,90449251200,169107043478365440,

%T 6267416821165079203599360,4435711276305905572695127676467200,

%U 58393052751308545653929138771580386824519680,14021772793551297695593332913856884153315254190271692800,60498832138791357698014788383803842810832836262245623803123983974400

%N Number of Eulerian circuits on the complete graph K_{2n+1}, divided by (n-1)!^(2n+1).

%D D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.3, p. 745, Problem 107.

%D B. D. McKay, Applications of a technique for labeled enumeration, Congress. Numerantium, 40 (1983), 207-221.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Brendan D. McKay and Robert W. Robinson, <a href="http://users.cecs.anu.edu.au/~bdm/papers/euler.pdf">Asymptotic enumeration of Eulerian circuits in the complete graph</a>, Combinatorics, Probability and Computing, 7 (1998), 437-449. (gives terms up to n=10, i.e., up through K_{21})

%F a(n) = A135388(n) / (n-1)!^(2n+1) = A350028(2n+1) / (n-1)!^(2n+1) = A357887(2n+1,n(2n+1)) / (n-1)!^(2n+1). - _Max Alekseyev_, Oct 19 2022

%e From _Günter Rote_, Dec 09 2021: (Start)

%e For n=2, in the graph K5, if we fix the Euler tour to start with the edge 12, we get 132 Euler tours. Here are the first and the last few in lexicographic order.

%e 12314253451

%e 12314254351

%e 12314352451

%e 12314354251

%e 12314524351

%e ...

%e 12543153241

%e 12543241351

%e 12543241531

%e 12543513241

%e 12543514231.

%e To get all 264*1!^5 = 264 Euler tours, the number must be multiplied by 2 to include the reversed tours. (End)

%o (Python)

%o # for n <= 4

%o def A(n,w="12"):

%o if len(w) > (2*n+1)*n: return 2

%o return sum(A(n, w+t) for t in "123456789"[:2*n+1]

%o if t!=w[-1] and t+w[-1] not in w and w[-1]+t not in w)

%Y Cf. A135388, A232545, A350028, A356366, A357855, A357856, A357857, A357885, A357886, A357887.

%K nonn,nice,walk

%O 1,1

%A _N. J. A. Sloane_, _Mira Bernstein_

%E More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 28 2003