login
A232545
Number of Euler tours of the complete digraph on n vertices.
11
1, 3, 256, 972000, 247669456896, 6022251970560000000, 18932148110851728998400000000, 10036271333655026636037644353536000000000, 1135547314049215265041779022180122624000000000000000000, 33878761698754076709292639330840075944838638855101181276979200000000000
OFFSET
2,2
LINKS
Wikipedia, BEST Theorem, a formula for counting Euler tours in digraphs.
FORMULA
a(n) = n^(n-2)*(n-2)!^n, by the "BEST Theorem". - James Thompson, Jul 18 2017, Günter Rote, Dec 09 2021
The above formula can be written as a(n) = A000272(n)*A000142(n-2)^n. - Omar E. Pol, Jul 18 2017
EXAMPLE
For n = 2, there is one Euler tour, (1,2,1), since (1,2,1) is cyclically equivalent to (2,1,2).
For n = 3, there are three Euler tours: (1,2,1,3,2,3,1), (1,2,3,1,3,2,1), (1,2,3,2,1,3,1).
PROG
(Python for n <= 5)
def A(n, w='12'):
if len(w) > n*(n-1): return 1
extensions = (w+t for t in '12345'[:n] if w[-1]!=t and w[-1]+t not in w)
return sum(A(n, z) for z in extensions)
(PARI) a(n) = n^(n-2)*(n-2)!^n \\ Andrew Howroyd, Dec 28 2021
CROSSREFS
Sequence in context: A059947 A203495 A051490 * A177748 A283018 A003381
KEYWORD
nonn,walk
AUTHOR
Tomas Boothby, Nov 25 2013
EXTENSIONS
a(5) corrected by Tomas Boothby, Dec 03 2013
Terms a(8) and beyond from Andrew Howroyd, Dec 28 2021
STATUS
approved