A232545 - OEIS

%I #47 Dec 28 2021 13:31:48

%S 1,3,256,972000,247669456896,6022251970560000000,

%T 18932148110851728998400000000,

%U 10036271333655026636037644353536000000000,1135547314049215265041779022180122624000000000000000000,33878761698754076709292639330840075944838638855101181276979200000000000

%N Number of Euler tours of the complete digraph on n vertices.

%H Andrew Howroyd, <a href="/A232545/b232545.txt">Table of n, a(n) for n = 2..30</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/BEST_theorem">BEST Theorem</a>, a formula for counting Euler tours in digraphs.

%F a(n) = n^(n-2)*(n-2)!^n, by the "BEST Theorem". - _James Thompson_, Jul 18 2017, _Günter Rote_, Dec 09 2021

%F The above formula can be written as a(n) = A000272(n)*A000142(n-2)^n. - _Omar E. Pol_, Jul 18 2017

%e For n = 2, there is one Euler tour, (1,2,1), since (1,2,1) is cyclically equivalent to (2,1,2).

%e 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).

%o (Python for n <= 5)

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

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

%o     extensions = (w+t for t in '12345'[:n] if w[-1]!=t and w[-1]+t not in w)

%o     return sum(A(n,z) for z in extensions)

%o (PARI) a(n) = n^(n-2)*(n-2)!^n \\ _Andrew Howroyd_, Dec 28 2021

%K nonn,walk

%O 2,2

%A _Tomas Boothby_, Nov 25 2013

%E a(5) corrected by _Tomas Boothby_, Dec 03 2013

%E Terms a(8) and beyond from _Andrew Howroyd_, Dec 28 2021