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

1, 3, 256, 972000, 247669456896, 6022251970560000000, 18932148110851728998400000000, 10036271333655026636037644353536000000000, 1135547314049215265041779022180122624000000000000000000, 33878761698754076709292639330840075944838638855101181276979200000000000

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

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

Adjacent sequences: A232542 A232543 A232544 * A232546 A232547 A232548

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