A350028 Number of Euler tours of the complete graph on n vertices (minus a matching if n is even).

2, 2, 264, 744, 129976320, 1847500800, 911520057021235200

Offset

3,1

Links

Table of n, a(n) for n=3..9.

Formula

a(2n+1) = A135388(n) = A357887(2n+1,n(2n+1)) = A007082(n) * (n-1)!^(2*n+1); a(2n) = A357887(2n,2n(n-1)) / (2n-1)!!. - Max Alekseyev, Oct 19 2022

Example

For n=6, if the edges 12,34,56 are removed from the complete graph and we fix
the tour to start with the edge 13, we get 372 Euler tours. Here are the first and the last few in lexicographic order.
  1324152635461
  1324152645361
  1324153625461
  1324153645261
  1324154625361
  1324154635261
  1324162536451
  ...
  1364532516241
  1364532614251
  1364532615241.
This must be multiplied by 2 to account for the reversed tours, for a total of 744.

Prog

(Python)
# for 3 <= n <= 9
def A(n, w="13"):
    if n%2==0 and len(w) > n*(n-1)//2 - n//2: return 2
    if n%2==1 and len(w) > n*(n-1)//2: return 2
    return sum(A(n, w+t) for t in "123456789"[:n]
        if t!=w[-1] and t+w[-1] not in w and w[-1]+t not in w
        and (n%2==1 or t+w[-1] not in "121 343 565 787"))

Crossrefs

Cf. A007082, A135388, A232545, A356366, A357855, A357856, A357857, A357885, A357886, A357887.

Sequence in context: A068103 A335257 A119512 * A262058 A067091 A334599

Adjacent sequences: A350025 A350026 A350027 * A350029 A350030 A350031

Keyword

nonn,walk,hard,more

Author

Günter Rote, Dec 08 2021

Status

approved