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

2, 264, 1015440, 90449251200, 169107043478365440, 6267416821165079203599360, 4435711276305905572695127676467200, 58393052751308545653929138771580386824519680, 14021772793551297695593332913856884153315254190271692800, 60498832138791357698014788383803842810832836262245623803123983974400

Offset

1,1

References

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

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

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

Links

Table of n, a(n) for n=1..10.

Brendan D. McKay and Robert W. Robinson, Asymptotic enumeration of Eulerian circuits in the complete graph, Combinatorics, Probability and Computing, 7 (1998), 437-449. (gives terms up to n=10, i.e., up through K_{21})

Formula

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

Example

From Günter Rote, Dec 09 2021: (Start)
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.
  12314253451
  12314254351
  12314352451
  12314354251
  12314524351
  ...
  12543153241
  12543241351
  12543241531
  12543513241
  12543514231.
To get all 264*1!^5 = 264 Euler tours, the number must be multiplied by 2 to include the reversed tours. (End)

Prog

(Python)
# for n <= 4
def A(n, w="12"):
    if len(w) > (2*n+1)*n: return 2
    return sum(A(n, w+t) for t in "123456789"[:2*n+1]
        if t!=w[-1] and t+w[-1] not in w and w[-1]+t not in w)

Crossrefs

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

Sequence in context: A236437 A137105 A216984 * A135388 A238983 A188964

Adjacent sequences: A007079 A007080 A007081 * A007083 A007084 A007085

Keyword

nonn,nice,walk

Author

N. J. A. Sloane, Mira Bernstein

Extensions

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

Status

approved