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

Author

Günter Rote, Dec 08 2021

Keywords

• nonn
• walk
• hard

Comments

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

Examples

			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.
		

Links

• Eric Weisstein, Cocktail Party Graph, MathWorld.

Crossrefs

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

Programs

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"))

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

Extensions

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