login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A033678 Number of labeled Eulerian graphs with n nodes.
(Formerly M3146)
8
1, 0, 1, 3, 38, 720, 26614, 1858122, 250586792, 66121926720, 34442540326456, 35611003057733928, 73321307277341501168, 301201690357187097528960, 2471354321681605983102370864, 40525241311304939167532163726672 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,4
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
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.
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 *)
PROG
(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
CROSSREFS
Cf. A228550 (with multiple components)
Row sums of A341743.
Sequence in context: A199025 A265914 A005780 * A228697 A072331 A109518
KEYWORD
easy,nonn,nice
AUTHOR
N. J. A. Sloane and Geoffrey Mess (mess(AT)math.ucla.edu)
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 03:33 EDT 2024. Contains 370952 sequences. (Running on oeis4.)