|
%I #24 Oct 21 2022 14:30:03
%S 2,2,264,744,129976320,1847500800,911520057021235200
%N Number of Euler tours of the complete graph on n vertices (minus a matching if n is even).
%F 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
%e For n=6, if the edges 12,34,56 are removed from the complete graph and we fix
%e the tour to start with the edge 13, we get 372 Euler tours. Here are the first and the last few in lexicographic order.
%e 1324152635461
%e 1324152645361
%e 1324153625461
%e 1324153645261
%e 1324154625361
%e 1324154635261
%e 1324162536451
%e ...
%e 1364532516241
%e 1364532614251
%e 1364532615241.
%e This must be multiplied by 2 to account for the reversed tours, for a total of 744.
%o (Python)
%o # for 3 <= n <= 9
%o def A(n,w="13"):
%o if n%2==0 and len(w) > n*(n-1)//2 - n//2: return 2
%o if n%2==1 and len(w) > n*(n-1)//2: return 2
%o return sum(A(n, w+t) for t in "123456789"[:n]
%o if t!=w[-1] and t+w[-1] not in w and w[-1]+t not in w
%o and (n%2==1 or t+w[-1] not in "121 343 565 787"))
%Y Cf. A007082, A135388, A232545, A356366, A357855, A357856, A357857, A357885, A357886, A357887.
%K nonn,walk,hard,more
%O 3,1
%A _Günter Rote_, Dec 08 2021
|
