A033678 Number of labeled Eulerian graphs with n nodes.

1, 0, 1, 3, 38, 720, 26614, 1858122, 250586792, 66121926720, 34442540326456, 35611003057733928, 73321307277341501168, 301201690357187097528960, 2471354321681605983102370864, 40525241311304939167532163726672

Offset: 1

Author

N. J. A. Sloane and Geoffrey Mess (mess(AT)math.ucla.edu)

Keywords

• easy
• nonn
• nice

Comments

From Petros Hadjicostas, Feb 20 2021: (Start)

See the comments for A058878 about the different (and sometimes confusing) terminology regarding even and (connected or not) Euler graphs.

Cao (2002) uses the term "connected labeled Eulerian graphs" in the title of his Section 4.3, where this sequence appears, and the term "labeled Eulerian graph" in some of the discussion of that section. The author does cite the definition of Harary and Palmer (1973) for an Euler or Eulerian graph (as a connected even graph).

Note that all graphs counted by this sequence, by A058878, and by the triangular arrays A228550 and A341743 are assumed to be simple (with no loops and no multiple edges). Read (1962), however, indicates how to solve similar counting problems in the case of graphs with loops and/or multiple edges. (End)

References

• F. Harary and E. Palmer, Graphical Enumeration, (1973), p. 12, Eq. (1.4.6).
• E. M. Palmer in L. W. Beineke and R. J. Wilson, Selected Topics in Graph Theory, Academic Press, NY, 1978, p. 385ff.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n=1..50
• Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.
• Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]
• math.stackexchange.com, Is it possible disconnected graph has euler circuit? [sic], August 30, 2015.
• Ronald C. Read, Euler graphs on labelled nodes, Canadian Journal of Mathematics, 14 (1962), 482-486; see the discussion in Section 4, following Eq. (8) on p. 486.

Crossrefs

Cf. A228550 (with multiple components)

Row sums of A341743.

Programs

Maple

A033678 := proc(n) option remember; local k; if n=1 then 1 else 2^binomial(n-1,2)-(1/n)*add(k*binomial(n,k)*2^binomial(n-k-1,2)*A033678(k),k=1..n-1); fi; end;

Mathematica

n = 16; (Series[ Log[ 1 + Sum[ 2^( (p-1)(p-2)/2 )x^p/(p!), {p, 1, n} ] ], {x, 0, n} ] // CoefficientList[#, x]& // Rest) * Range[n]! (* truncated exponential generating function *)
(* Second program: *)
a[n_] := a[n] = If[n == 1, 1, 2^Binomial[n-1, 2]-(1/n)*Sum[k*Binomial[n, k]*2^Binomial[n-k-1, 2]*a[k], {k, 1, n-1}]]; Table[a[n], {n, 1, 16}] (* Jean-François Alcover, Feb 11 2014, after Maple *)

Sage

@cached_function
def A033678(n):
    if n == 1: return 1
    return 2^binomial(n-1, 2)-sum(k*2^((k-n+1)*(k-n+2)/2)*binomial(n,k)*A033678(k) for k in (1..n-1))/n
[A033678(n) for n in (1..16)] # Peter Luschny, Jan 17 2016