A382362 Number of oriented Eulerian circuits from a fixed start vertex in the complete digraph K_n, counting distinct first arcs.
1, 6, 768, 3888000, 1238347284480, 36133511823360000000, 132525036775962102988800000000, 80290170669240213088301154828288000000000, 10219925826442937385376011199621103616000000000000000000, 338787616987540767092926393308400759448386388551011812769792000000000000
Offset: 2
Examples
For n=3, the complete digraph K_3 with vertex set {1,2,3} has 6 distinct Eulerian circuits (counting rotations / distinct first arcs) starting and ending at vertex 1: (1,2,3,1,3,2,1), (1,3,2,1,2,3,1), (1,2,1,3,2,3,1), (1,3,2,3,1,2,1), (1,2,3,2,1,3,1), and (1,3,1,2,3,2,1).
The first two are equal to their reversals. The others form pairs that are equal in reversed form. Since this sequence distinguishes arc order and direction, a(3)=6 rather than 4.
In contrast, A232545 counts only 3 tours for n=3 because it does not distinguish Eulerian circuits that differ solely by rotating the cycle to a different first arc out of vertex 1.
Links
- Wikipedia, BEST Theorem.
Programs
-
Haskell
a n = (n-1) * n^(n-2) * (product [1..(n-2)])^n
-
PARI
a(n) = (n-1) * n^(n-2) * factorial(n-2)^n;