cp's OEIS Frontend

A003049 Number of connected Eulerian graphs with n unlabeled nodes.

%I A003049 M3344 #79 Feb 16 2025 08:32:27
%S A003049 1,0,1,1,4,8,37,184,1782,31026,1148626,86539128,12798435868,
%T A003049 3620169692289,1940367005824561,1965937435288738165,
%U A003049 3766548132138130650270,13666503289976224080346733
%N A003049 Number of connected Eulerian graphs with n unlabeled nodes.
%C A003049 These are connected graphs with every node of even degree (cf. A002854).
%D A003049 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 117.
%D A003049 Valery A. Liskovets, Enumeration of Euler graphs. (Russian), Vesci Akad. Navuk BSSR, Ser. Fiz.-Mat. Navuk 1970, No.6, 38-46 (1970). Math. Rev., Vol. 44, 1972, p. 1195, #6557.
%D A003049 R. W. Robinson, Enumeration of Euler graphs, pp. 147-153 of F. Harary, editor, Proof Techniques in Graph Theory. Academic Press, NY, 1969.
%D A003049 R. W. Robinson, personal communication.
%D A003049 R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1979.
%D A003049 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003049 Chai Wah Wu, <a href="/A003049/b003049.txt">Table of n, a(n) for n = 1..88</a> (terms 1..60 from Max Alekseyev)
%H A003049 P. J. Cameron, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H A003049 Erich Friedman, <a href="/A003049/a003049.gif">Illustration of initial terms</a>
%H A003049 V. A. Liskovec, <a href="/A002854/a002854.pdf">Enumeration of Euler Graphs</a>, (in Russian), Akademiia Navuk BSSR, Minsk., 6 (1970), 38-46. (annotated scanned copy)
%H A003049 C. L. Mallows and N. J. A. Sloane, <a href="http://www.jstor.org/stable/2100368">Two-graphs, switching classes and Euler graphs are equal in number</a>, SIAM J. Appl. Math., 28 (1975), 876-880.
%H A003049 C. L. Mallows and N. J. A. Sloane, Two-graphs, switching classes and Euler graphs are equal in number, SIAM J. Appl. Math., 28 (1975), 876-880. [Copy on N. J. A. Sloane's Home Page]
%H A003049 Brendan McKay, <a href="http://users.cecs.anu.edu.au/~bdm/data/">Combinatorial Data (Eulerian graphs)</a>.
%H A003049 R. W. Robinson, <a href="/A003049/a003049.pdf">Enumeration of Euler graphs</a>, pp. 147-153 of F. Harary, editor, Proof Techniques in Graph Theory. Academic Press, NY, 1969. (Annotated scanned copy)
%H A003049 Peter Steinbach, <a href="/A000088/a000088_17.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H A003049 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/EulerianGraph.html">Eulerian Graph.</a>
%F A003049 Let B(x) = g.f. for A002854. Then g.f. A(x) for A003049 satisfies 1 + B(x) = exp(Sum_{n>=1} A(x^n)/n). - Robinson (1969).
%F A003049 Inverse Euler transform of A002854. (This is equivalent to the Robinson formula.) - _Franklin T. Adams-Watters_, Jul 24 2006
%F A003049 Let B(x) = g.f. for A002854. Then A(x) = Sum_{m >= 1} (mu(m)/m) * log(1 + B(x^m)), where mu(m) = A008683(m). (This is essentially a re-statement of the equation on p. 151 in Robinson (1969).) - _Petros Hadjicostas_, Feb 24 2021
%t A003049 A002854 = Import["https://oeis.org/A002854/b002854.txt", "Table"][[All, 2]];
%t A003049 (* EulerInvTransform is defined in A022562 *)
%t A003049 EulerInvTransform[A002854] (* _Jean-François Alcover_, Aug 27 2019, updated Mar 17 2020 *)
%o A003049 (Python)
%o A003049 from functools import lru_cache
%o A003049 from itertools import combinations
%o A003049 from fractions import Fraction
%o A003049 from math import prod, gcd, factorial
%o A003049 from sympy import mobius, divisors
%o A003049 from sympy.utilities.iterables import partitions
%o A003049 def A003049(n):
%o A003049     @lru_cache(maxsize=None)
%o A003049     def b(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum(((q>>1)-1)*r+(q*r*(r-1)>>1) for q, r in p.items())+any(q&1 for q in p),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n)))
%o A003049     @lru_cache(maxsize=None)
%o A003049     def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
%o A003049     return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n # _Chai Wah Wu_, Jul 03 2024
%Y A003049 Cf. A002854, A008683.
%K A003049 nonn,nice,easy
%O A003049 1,5
%A A003049 _N. J. A. Sloane_
%E A003049 a(1)-a(26) were computed by R. W. Robinson
%E A003049 More terms from _Vladeta Jovovic_, Apr 18 2000