OFFSET
2,2
LINKS
Andrew Howroyd, Table of n, a(n) for n = 2..30
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
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
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