cp's OEIS Frontend

A232545 Number of Euler tours of the complete digraph on n vertices.

%I A232545 #47 Dec 28 2021 13:31:48
%S A232545 1,3,256,972000,247669456896,6022251970560000000,
%T A232545 18932148110851728998400000000,
%U A232545 10036271333655026636037644353536000000000,1135547314049215265041779022180122624000000000000000000,33878761698754076709292639330840075944838638855101181276979200000000000
%N A232545 Number of Euler tours of the complete digraph on n vertices.
%H A232545 Andrew Howroyd, <a href="/A232545/b232545.txt">Table of n, a(n) for n = 2..30</a>
%H A232545 Wikipedia, <a href="https://en.wikipedia.org/wiki/BEST_theorem">BEST Theorem</a>, a formula for counting Euler tours in digraphs.
%F A232545 a(n) = n^(n-2)*(n-2)!^n, by the "BEST Theorem". - _James Thompson_, Jul 18 2017, _Günter Rote_, Dec 09 2021
%F A232545 The above formula can be written as a(n) = A000272(n)*A000142(n-2)^n. - _Omar E. Pol_, Jul 18 2017
%e A232545 For n = 2, there is one Euler tour, (1,2,1), since (1,2,1) is cyclically equivalent to (2,1,2).
%e A232545 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 A232545 (Python for n <= 5)
%o A232545 def A(n,w='12'):
%o A232545     if len(w) > n*(n-1): return 1
%o A232545     extensions = (w+t for t in '12345'[:n] if w[-1]!=t and w[-1]+t not in w)
%o A232545     return sum(A(n,z) for z in extensions)
%o A232545 (PARI) a(n) = n^(n-2)*(n-2)!^n \\ _Andrew Howroyd_, Dec 28 2021
%K A232545 nonn,walk
%O A232545 2,2
%A A232545 _Tomas Boothby_, Nov 25 2013
%E A232545 a(5) corrected by _Tomas Boothby_, Dec 03 2013
%E A232545 Terms a(8) and beyond from _Andrew Howroyd_, Dec 28 2021