cp's OEIS Frontend

A033678 Number of labeled Eulerian graphs with n nodes.

%I A033678 M3146 #35 Feb 20 2021 16:10:47
%S A033678 1,0,1,3,38,720,26614,1858122,250586792,66121926720,34442540326456,
%T A033678 35611003057733928,73321307277341501168,301201690357187097528960,
%U A033678 2471354321681605983102370864,40525241311304939167532163726672
%N A033678 Number of labeled Eulerian graphs with n nodes.
%C A033678 From _Petros Hadjicostas_, Feb 20 2021: (Start)
%C A033678 See the comments for A058878 about the different (and sometimes confusing) terminology regarding even and (connected or not) Euler graphs.
%C A033678 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).
%C A033678 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)
%D A033678 F. Harary and E. Palmer, Graphical Enumeration, (1973), p. 12, Eq. (1.4.6).
%D A033678 E. M. Palmer in L. W. Beineke and R. J. Wilson, Selected Topics in Graph Theory, Academic Press, NY, 1978, p. 385ff.
%D A033678 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A033678 T. D. Noe, <a href="/A033678/b033678.txt">Table of n, a(n) for n=1..50</a>
%H A033678 Huantian Cao, <a href="http://cobweb.cs.uga.edu/~rwr/STUDENTS/hcao.html">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, thesis, 2002.
%H A033678 Huantian Cao, <a href="/A000009/a000009.pdf">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, thesis, 2002 [Local copy, with permission]
%H A033678 math.stackexchange.com, <a href="https://math.stackexchange.com/questions/1414667/is-it-possible-disconnected-graph-has-euler-circuit">Is it possible disconnected graph has euler circuit? [sic]</a>, August 30, 2015.
%H A033678 Ronald C. Read, <a href="https://doi.org/10.4153/CJM-1962-039-0">Euler graphs on labelled nodes</a>, Canadian Journal of Mathematics, 14 (1962), 482-486; see the discussion in Section 4, following Eq. (8) on p. 486.
%p A033678 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;
%t A033678 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 *)
%t A033678 (* Second program: *)
%t A033678 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 *)
%o A033678 (Sage)
%o A033678 @cached_function
%o A033678 def A033678(n):
%o A033678     if n == 1: return 1
%o A033678     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
%o A033678 [A033678(n) for n in (1..16)] # _Peter Luschny_, Jan 17 2016
%Y A033678 Cf. A228550 (with multiple components)
%Y A033678 Row sums of A341743.
%K A033678 easy,nonn,nice
%O A033678 1,4
%A A033678 _N. J. A. Sloane_ and Geoffrey Mess (mess(AT)math.ucla.edu)