A357857 -id:A357857 - 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

A007082 Number of Eulerian circuits on the complete graph K_{2n+1}, divided by (n-1)!^(2n+1).

Original entry on oeis.org

2, 264, 1015440, 90449251200, 169107043478365440, 6267416821165079203599360, 4435711276305905572695127676467200, 58393052751308545653929138771580386824519680, 14021772793551297695593332913856884153315254190271692800, 60498832138791357698014788383803842810832836262245623803123983974400

Offset: 1

N. J. A. Sloane, Mira Bernstein

			From _Günter Rote_, Dec 09 2021: (Start)
For n=2, in the graph K5, if we fix the Euler tour to start with the edge 12, we get 132 Euler tours. Here are the first and the last few in lexicographic order.
  12314253451
  12314254351
  12314352451
  12314354251
  12314524351
  ...
  12543153241
  12543241351
  12543241531
  12543513241
  12543514231.
To get all 264*1!^5 = 264 Euler tours, the number must be multiplied by 2 to include the reversed tours. (End)

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.3, p. 745, Problem 107.
B. D. McKay, Applications of a technique for labeled enumeration, Congress. Numerantium, 40 (1983), 207-221.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Florian Ragwitz, Table of n, a(n) for n = 1..16
Brendan D. McKay and Robert W. Robinson, Asymptotic enumeration of Eulerian circuits in the complete graph, Combinatorics, Probability and Computing, 7 (1998), 437-449. (gives terms up to n=10, i.e., up through K_{21})

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

# for n <= 4
def A(n,w="12"):
    if len(w) > (2*n+1)*n: return 2
    return sum(A(n, w+t) for t in "123456789"[:2*n+1]
        if t!=w[-1] and t+w[-1] not in w and w[-1]+t not in w)

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

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 28 2003

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

A089243 Number of partitions into strokes of the star graph with n edges on the plane, up to rotations and reflections around the center node.

Original entry on oeis.org

1, 2, 3, 4, 9, 22, 61, 200, 689, 3054, 12110, 61132, 274264, 1515134, 7498195, 44301928, 238206692, 1490114770, 8605537805, 56612534420, 348083793872, 2396294898646, 15577794980189, 111781094032984, 763986810923430, 5695585712379834

Offset: 0

Yasutoshi Kohmoto

A "stroke" is defined as follows. If the following conditions are satisfied then the partition to directed paths on a directed graph is called "a partition to strokes on a directed graph", and all directed paths in the partition are called "strokes". C.1. Two different directed paths in a partition do not have the same edges. C.2. A union of two different paths in a partition does not become a directed path. In other words, a "stroke" is a locally maximal path on a directed graph.
This sequence has its origin in the strokes made when writing Japanese Kanji.
The value a(1) is ambiguous as it depends on the definition of the star graph with n = 1 edge. If one of the edge endpoints is labeled as the star center, then we have the current value a(1) = 2. However, if the center is not distinguished, then a(1) would be 1. - Max Alekseyev, May 04 2023

			For n = 3, call the center node "0" and the terminal nodes "1", "2", "3".
Four partitions exist as follows:
  {1->0->2, 0->3}
  {1->0->2, 3->0}
  {1->0, 2->0, 3->0}
  {0->1, 0->2, 0->3}.
So a(3) = 4.

Christian Sievers, Table of n, a(n) for n = 0..728

Cf. A131518, A131520, A354228, A131709, A357857, A357895.

p(n,t,o)=o*sum(k=0,(n-1)/2,n!/(k!*(n-2*k)!)*t^k)+if(n%2==0, n!/(n/2)!*t^(n/2));
a(n)=if(n==0,1,(sumdiv(n,d,eulerphi(n/d)*p(d,n/d,2)) + if(n%2,2*n*p((n-1)/2,2,1),n/2*p(n/2,2,2)+n*p(n/2-1,2,2)+n*p(n/2-1,2,1)))/(2*n)) \\ Christian Sievers, May 14 2023

Edited, terms a(0)-a(1) and a(6) corrected, a(7)-a(13) added by Max Alekseyev, Oct 20 2022

More terms from Christian Sievers, May 14 2023

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

A007082 Number of Eulerian circuits on the complete graph K_{2n+1}, divided by (n-1)!^(2n+1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Python

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