A007082 -id:A007082 - cp's OEIS frontend

A135388 Number of (directed) Eulerian circuits on the complete graph K_{2n+1}.

2, 264, 129976320, 911520057021235200, 257326999238092967427785160130560, 6705710151431658873046319662156165939200000000000000, 32132958735643556926111996291480203406145819659840760945049600000000000000000

Offset: 1

Max Alekseyev, Dec 10 2007

B. D. McKay, Applications of a technique for labeled enumeration, Congress. Numerantium, 40 (1983), 207-221.

Max Alekseyev, Table of n, a(n) for n = 1..10
Brendan D. McKay and Robert W. Robinson, Asymptotic enumeration of Eulerian circuits in the complete graph, Combinatorics, Probability and Computing, 7 (1998), 437-449.
G. Tarry, Géométrie de situation: Nombre de manières distinctes de parcourir en une seule course toutes les allées d'un labyrinthe rentrant, en ne passant qu'une seule fois par chacune des allées, Comptes Rendus Assoc. Franç. Avance. Sci. 15, part 2 (1886), pp. 49-53.
Eric Weisstein's World of Mathematics, Complete Graph
Eric Weisstein's World of Mathematics, Eulerian Cycle

Bisection of A350028.
Cf. A007082, A232545, A357856, A357857, A356366, A357855, A357885, A357886, A357887.
Cf. A369820 (undirected Eulerian circuits).

Table[2 Length[FindEulerianCycle[CompleteGraph[2 n + 1], All]], {n, 3}] (* Eric W. Weisstein, Jan 09 2018 *)
  (* a(3) requires a very large amount of memory *)

a(n) = A007082(n) * (n-1)!^(2*n+1).

a(n) = A350028(2n+1) = A357887(2n+1,n(2n+1)). - Max Alekseyev, Oct 19 2022

A357857 Number of (open and closed) trails in the complete undirected graph on n labeled vertices.

Original entry on oeis.org

1, 4, 21, 232, 14425, 3653196, 17705858989, 261353065517776, 241809117107232026097

Offset: 1

Max Alekseyev, Oct 16 2022

Trails are directed and pass through each (undirected) edge at most once in either of the two directions.

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

a(n) = n * A357855(n) + n * (n-1) * A357856(n).

a(9) from Bert Dobbelaere, Oct 17 2022

A357885 Triangle read by rows: T(n,k) = number of closed trails of length k starting and ending at a fixed vertex in the complete undirected graph on n labeled vertices, for n >= 1 and k = 0 .. n(n-1)/2.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 2, 1, 0, 0, 6, 6, 0, 0, 1, 0, 0, 12, 24, 24, 72, 168, 0, 0, 528, 1, 0, 0, 20, 60, 120, 480, 1680, 3120, 5760, 15840, 29040, 22320, 0, 0, 0, 1, 0, 0, 30, 120, 360, 1800, 8280, 27360, 88560, 310320, 934560, 2296800, 5541120, 12965760, 21837600, 27740160, 58752000, 101882880, 0, 0, 389928960

Offset: 1

Max Alekseyev, Oct 18 2022

			Triangle starts:
 n=1: 1
 n=2: 1, 0
 n=3: 1, 0, 0, 2
 n=4: 1, 0, 0, 6, 6, 0, 0
 n=5: 1, 0, 0, 12, 24, 24, 72, 168, 0, 0, 528
 ...

Max Alekseyev, Table of n, a(n) for n = 1..175 (rows n=1..10)

Cf. A007082, A135388, A232545, A297383, A350028, A356366, A357855 (row sums), A357856, A357857, A357886, A357887.

For k >= 1, T(n,k) = A357887(n,k) * k / n.
Last nonzero element in row n:
 T(2n+1,n(2n+1)) = A135388(n) * n = A350028(2n+1) * n = A007082(n) * n * (n-1)!^(2*n+1);
 T(2n,2n(n-1)) = A350028(2n) * (n-1) * (2n-1)!! = A297383(n) * (2n-2) * (2n-1)!!.

A357886 Triangle read by rows: T(n,k) = number of open trails of length k starting and ending at fixed distinct vertices in the complete undirected graph on n labeled vertices, for n >= 1 and k = 0 .. n*(n-1)/2.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 0, 0, 1, 2, 2, 4, 6, 0, 0, 1, 3, 6, 18, 48, 78, 96, 132, 132, 0, 0, 1, 4, 12, 48, 180, 528, 1392, 3600, 7920, 13680, 21840, 31872, 25008, 0, 0, 0, 1, 5, 20, 100, 480, 1980, 7680, 29040, 100920, 316320, 923520, 2502000, 6011760, 12584880, 23417280, 38196480, 50112000, 53667840, 64988160, 64988160, 0

Offset: 1

Max Alekseyev, Oct 19 2022

			Triangle T(n,k) starts with:
n=1: 0,
n=2: 0, 1,
n=3: 0, 1, 1, 0,
n=4: 0, 1, 2, 2, 4, 6, 0,
n=5: 0, 1, 3, 6, 18, 48, 78, 96, 132, 132, 0,
...

Max Alekseyev, Table of m, a(m) for m = 1..129 (rows n = 1..9)

Cf. A007082, A135388, A232545, A350028, A357855, A357856 (row sums), A357857, A356366, A357885, A357887.

A357887 Triangle read by rows: T(n,k) = number of circuits of length k in the complete undirected graph on n labeled vertices, for n >= 1 and k = 0 .. n(n-1)/2.

Original entry on oeis.org

1, 2, 0, 3, 0, 0, 2, 4, 0, 0, 8, 6, 0, 0, 5, 0, 0, 20, 30, 24, 60, 120, 0, 0, 264, 6, 0, 0, 40, 90, 144, 480, 1440, 2340, 3840, 9504, 15840, 11160, 0, 0, 0, 7, 0, 0, 70, 210, 504, 2100, 8280, 23940, 68880, 217224, 594720, 1339800, 2983680, 6482880, 10190880, 12136320, 24192000, 39621120, 0, 0, 129976320

Offset: 1

Max Alekseyev, Oct 19 2022

A circuit of length k is viewed as a sequence of k+1 vertices it visits modulo cyclic rotations. Hence T(n,0) = n enumerates individual vertices.

			Triangle T(n,k) starts with:
 n=1: 1,
 n=2: 2, 0,
 n=3: 3, 0, 0, 2,
 n=4: 4, 0, 0, 8, 6, 0, 0,
 n=5: 5, 0, 0, 20, 30, 24, 60, 120, 0, 0, 264,
 ...

Max Alekseyev, Table of n, a(n) for n = 1..175 (rows n=1..10)

Cf. A007082, A135388, A232545, A297383, A350028, A356366 (row sums), A357855, A357856, A357857, A357885, A357886.

For k >= 1, T(n,k) = A357885(n,k) * n / k.
Last nonzero element in row n:
 T(2n+1,n(2n+1)) = A135388(n) = A350028(2n+1) = A007082(n) * (n-1)!^(2*n+1);
 T(2n,2n(n-1)) = A350028(2n) * (2n-1)!! = A297383(n) * 2 * (2n-1)!!.

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

Original entry on oeis.org

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

Offset: 1

Günter Rote, Dec 08 2021

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

			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.

Eric Weisstein, Cocktail Party Graph, MathWorld.

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

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

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

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

A356366 Number of (directed) circuits in the complete undirected graph on n labeled vertices.

Original entry on oeis.org

1, 2, 5, 18, 523, 44884, 227838935, 1086696880188, 1566338449874827101, 694432397394116143569646

Offset: 1

Max Alekseyev, Oct 16 2022

In other words, number of closed trails up to cyclic rotations (cf. A357855).

			For n = 3, we have 5 circuits: 3 of length 0 (singleton vertices), and 2 of length 3 (1->2->3->1 and 1->3->2->1).

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

a(n) = Sum_{k = 0..n(n-1)/2} A357887(n,k) = n + n * Sum_{k = 1..n(n-1)/2} A357885(n,k) / k.

a(9) from Bert Dobbelaere, Oct 17 2022

a(10) from Max Alekseyev, Jul 17 2025

A357855 Number of closed trails starting and ending at a fixed vertex in the complete undirected graph on n labeled vertices.

Original entry on oeis.org

1, 1, 3, 13, 829, 78441, 622316671, 3001764349333, 5926347237626029593, 2616519370820267981798929

Offset: 1

Max Alekseyev, Oct 16 2022

Trails are directed and pass through each (undirected) edge at most once in either of the two directions.

			For n = 3, we have a(3) = 3 trails starting and ending at vertex 1: 1 (single vertex), 1->2->3->1, and 1->3->2->1.

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

a(n) = Sum_{k = 0..n(n-1)/2} A357885(n,k) = 1 + Sum_{k = 1..n(n-1)/2} A357887(n,k) * k / n.

a(9) from Bert Dobbelaere, Oct 17 2022

a(10) from Max Alekseyev, Jul 17 2025

A357856 Number of trails between two fixed distinct vertices in the complete undirected graph on n labeled vertices.

Original entry on oeis.org

0, 1, 2, 15, 514, 106085, 317848626, 4238195548627, 2617666555119413330

Offset: 1

Max Alekseyev, Oct 16 2022

Trails are directed and pass through each (undirected) edge at most once in either of the two directions.

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

a(n) = Sum_{k = 0..n(n-1)/2} A357886(n,k).

a(9) from Bert Dobbelaere, Oct 17 2022

A284287 Number of possible legal open chains of a set of dominoes tiles with 0 to 2n pips.

Original entry on oeis.org

12, 126720, 7959229931520, 10752728122249860612096000, 829276462388385539562198269952000000000000, 7969891788752886799729592752113502210704733844275200000000000000, 18306383771271364475276585375748692499524930312437317320546133915243380736000000000000000000

Offset: 1

Amiram Eldar, Mar 24 2017

nonn

a(3) corresponds to the standard double-six set of 28 tiles. The question for its value was asked by Louis Poinsot in 1809 and by Orly Terquem in 1849 and was first calculated by Michel Reiss in 1859 (published in 1871).
The problem of finding a(2) appears in Henry Dudeney's book.
a(4) was calculated by Gaston Tarry in 1886.
The number of legally closed chains is a(n)/((n+1)*(2n+1)) = n^(2n+1) * A135388(n) (i.e., divided by the number of tiles in the set, A000217(2n+1)) = 2, 8448, 284258211840, 238949513827774680268800, ... .
If reverse order is not counted, the number of open chains is a(n)/2 = 6, 63360, 3979614965760, 5376364061124930306048000, ..., and the number of closed chains is a(n)/(2*(n+1)*(2n+1)) = 1, 4224, 142129105920, 119474756913887340134400, ... .

			For n=1 there is 1 basic chain of 6 tiles: (0|0)(0|1)(1|1)(1|2)(2|2)(2|0). There are 6 cyclic permutations and a 2nd version for each, in a reverse order, so a(1) = 1 * 6 * 2 = 12.

Henry Ernest Dudeney, "The Fifteen Dominoes", Amusements in Mathematics, Nelson, Edinburgh 1917, pp. 209-210.
Martin Gardner, Mathematical Circus, Alfred A. Knopf, NY, 1979, pp. 137-142.
Donald E. Knuth, The Art of Computer Programming, Volume 4A, Addison-Wesley, 2011, pp. 389 and 745.
K. W. H. Leeflang, Domino games and domino puzzles, St. Martin's Press, New York, 1975, Chapter VIII, section 1, pp. 125-134.
Édouard Lucas, "La géométrie des réseaux et le problème des dominos", Récréations mathématiques, Volume 4, Gauthier-Villars, Paris, 1894, pp. 125-129.
Yakov Perelman, Figures for Fun, Foreign Languages Publishing House, Moscow, 1957, p. 38.
Miodrag S. Petković, "Poinsot's Diagram-tracing Puzzle", Famous Puzzles of Great Mathematicians, Amer. Math. Soc. (AMS), Providence RI, 2009, pp. 245-247
Michel Reiss, Evaluation du nombre de combinaisons desquelles les 28 dés d'un jeu du Domino sont susceptibles d'après la règle de ce jeu, Annali di Matematica Pura ed Applicata, Vol. 5.1 (1871), pp. 63-120.
W. W. Rouse Ball and H. S. M. Coxeter, Mathematical Recreations and Essays, Dover NY, 1987, pp. 243-254.

Amiram Eldar, Table of n, a(n) for n = 1..10
Pierre Audibert, Enumeration of Eulerian Paths in Undirected Graphs, Mathematics for Informatics and Computer Science, Wiley, 2010, Chapter 36, Section 36.4.1., "Number of domino chains", pp. 813-816.
Philippe Chevanne, Eulériens (in French); Eulerian circuits (English translation, Wayback Machine link).
Henry Ernest Dudeney, The Fifteen Dominoes, Amusements in Mathematics, 1917.
Martin Gardner, A handful of combinatorial problems based on dominoes, Mathematical Games, Scientific American, Vol. 221, No. 6 (1969), pp. 122-127; JSTOR link.
Italo Ghersi, Matematica dilettevole e curiosa (in Italian), Hoepli, Milano, 1913, p. 695.
Allan J. Gottlieb, Streaker at the Banquet Table, Puzzle Corner, Technology Review, MIT, June 1976, pp. 64-69.
Donald E. Knuth, Generating all combinations, The Art of Computer Programming, Volume 4, Combinatorial Algorithms, p. 35 and 57.
Édouard Lucas, Récréations mathématiques, Vol. 4., pp. 125-129.
Brendan D. McKay and Robert W. Robinson, Asymptotic Enumeration of Eulerian Circuits in the Complete Graph, Combinatorics, Probability and Computing, Vol. 7, No. 4 (1998), pp. 437-449; author's copy.
L. Poinsot, Mémoire sur les polygones et les polyèdres, J. de l'Ecole Polytechnique, Volume 4 (1810) pp. 16—49.
M. Reiss, Evaluation du nombre de combinaisons desquelles les 28 dés d'un jeu du Domino sont susceptibles d'après la règle de ce jeu, Annali di Matematica Pura ed Applicata, Vol. 5.1 (1871), pp. 63-120; HathiTrust link.
G. Tarry, Géométrie de situation: Nombre de manières distinctes de parcourir en une seule course toutes les allées d'un labyrinthe rentrant, en ne passant qu'une seule fois par chacune des allées, Comptes Rendus Assoc. Franç. Avance. Sci. 15, part 2 (1886), pp. 49-53.
O. Terquem, Sur les polygones et les polyèdres étoilés, polygones funiculaires, Nouv. Ann. Math., Vol. 8 (1849), pp. 68-74.

Cf. A000217, A007082, A135388.

a(n) = (n+1)*(2n+1)*n^(2n+1)*A135388(n) = (n+1)*(2n+1)*n^(2n+1)*(n-1)!^(2n+1)*A007082(n).

cp's OEIS Frontend

A135388 Number of (directed) Eulerian circuits on the complete graph K_{2n+1}.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

A357857 Number of (open and closed) trails in the complete undirected graph on n labeled vertices.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A357885 Triangle read by rows: T(n,k) = number of closed trails of length k starting and ending at a fixed vertex in the complete undirected graph on n labeled vertices, for n >= 1 and k = 0 .. n(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A357886 Triangle read by rows: T(n,k) = number of open trails of length k starting and ending at fixed distinct vertices in the complete undirected graph on n labeled vertices, for n >= 1 and k = 0 .. n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

A357887 Triangle read by rows: T(n,k) = number of circuits of length k in the complete undirected graph on n labeled vertices, for n >= 1 and k = 0 .. n(n-1)/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A356366 Number of (directed) circuits in the complete undirected graph on n labeled vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A357855 Number of closed trails starting and ending at a fixed vertex in the complete undirected graph on n labeled vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A357856 Number of trails between two fixed distinct vertices in the complete undirected graph on n labeled vertices.

Views

Author

Keywords

Comments

Crossrefs

Formula