|
|
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
|
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
|
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
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
|
|
CROSSREFS
|
Cf. A228550 (with multiple components)
|
|
KEYWORD
|
easy,nonn,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|