%I M3344 #78 Jul 05 2024 02:02:22
%S 1,0,1,1,4,8,37,184,1782,31026,1148626,86539128,12798435868,
%T 3620169692289,1940367005824561,1965937435288738165,
%U 3766548132138130650270,13666503289976224080346733
%N Number of connected Eulerian graphs with n unlabeled nodes.
%C These are connected graphs with every node of even degree (cf. A002854).
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 117.
%D 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 R. W. Robinson, Enumeration of Euler graphs, pp. 147-153 of F. Harary, editor, Proof Techniques in Graph Theory. Academic Press, NY, 1969.
%D R. W. Robinson, personal communication.
%D R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1979.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H 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 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 Erich Friedman, <a href="/A003049/a003049.gif">Illustration of initial terms</a>
%H 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 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 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 Brendan McKay, <a href="http://users.cecs.anu.edu.au/~bdm/data/">Combinatorial Data (Eulerian graphs)</a>.
%H 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EulerianGraph.html">Eulerian Graph.</a>
%F 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 Inverse Euler transform of A002854. (This is equivalent to the Robinson formula.) - _Franklin T. Adams-Watters_, Jul 24 2006
%F 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 A002854 = Import["https://oeis.org/A002854/b002854.txt", "Table"][[All, 2]];
%t (* EulerInvTransform is defined in A022562 *)
%t EulerInvTransform[A002854] (* _Jean-François Alcover_, Aug 27 2019, updated Mar 17 2020 *)
%o (Python)
%o from functools import lru_cache
%o from itertools import combinations
%o from fractions import Fraction
%o from math import prod, gcd, factorial
%o from sympy import mobius, divisors
%o from sympy.utilities.iterables import partitions
%o def A003049(n):
%o @lru_cache(maxsize=None)
%o 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 @lru_cache(maxsize=None)
%o def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
%o return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n # _Chai Wah Wu_, Jul 03 2024
%Y Cf. A002854, A008683.
%K nonn,nice,easy
%O 1,5
%A _N. J. A. Sloane_
%E a(1)-a(26) were computed by R. W. Robinson
%E More terms from _Vladeta Jovovic_, Apr 18 2000
|