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

1, 1, 2, 2, 264, 744, 129976320, 1847500800, 911520057021235200, 91507897551783002112, 257326999238092967427785160130560, 234051620220909442615820736748584960, 6705710151431658873046319662156165939200000000000000

Offset

1,3

Comments

For even n, the graph is a cocktail party graph (cf. A297383). - Max Alekseyev, Jul 24 2025

Links

Table of n, a(n) for n=1..13.

Eric Weisstein, Cocktail Party Graph, MathWorld.

Formula

a(2n+1) = A135388(n) = A357887(2n+1,n(2n+1)) = A007082(n) * (n-1)!^(2*n+1); a(2n) = 2 * A297383(n) = 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, A297383, A334554, 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

Author

Günter Rote, Dec 08 2021

Extensions

a(1)-a(2) prepended, a(10)-a(13) added by Max Alekseyev, Jul 15 2025

Status

approved