A007082 Number of Eulerian circuits on the complete graph K_{2n+1}, divided by (n-1)!^(2n+1).
2, 264, 1015440, 90449251200, 169107043478365440, 6267416821165079203599360, 4435711276305905572695127676467200, 58393052751308545653929138771580386824519680, 14021772793551297695593332913856884153315254190271692800, 60498832138791357698014788383803842810832836262245623803123983974400
Offset: 1
Examples
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)
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
- Florian Ragwitz, Table of n, a(n) for n = 1..16
- 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})
Crossrefs
Programs
-
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)
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
Extensions
More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 28 2003