A007126 Number of connected rooted strength 1 Eulerian graphs with n nodes.

1, 0, 1, 1, 6, 18, 111, 839, 11076, 260327, 11698115, 1005829079, 163985322983, 50324128516939, 29000032348355991, 31395491269119883535, 63967623226983806252862, 245868096558697545918087280

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Comment from Valery Liskovets. Mar 13 2009: Here strength 1 means that the graph is a simple graph (i.e. without multiple edges and loops). Cf. the description of A002854 (number of Euler graphs); and the initial terms 1, 0, 1, 1, 6 can be easily verified. By the way, there is a simple bijective transformation of arbitrary n-graphs into rooted Eulerian (n+1)-graphs: add an external root-vertex and connect it to the odd-valent vertices.

References

• R. W. Robinson, personal communication.
• R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1979.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..88 (terms 1..26 from R. W. Robinson)

Crossrefs

Cf. A158007, A000088, A002854.

Programs

Mathematica

A000088 = Cases[Import["https://oeis.org/A000088/b000088.txt", "Table"], {, }][[All, 2]];
A002854 = Import["https://oeis.org/A002854/b002854.txt", "Table"][[All, 2]];
a[n_] := a[n] = A000088[[n]] - Sum[a[k] A002854[[n - k]], {k, 1, n - 1}];
Array[a, 18] (* Jean-François Alcover, Aug 29 2019, after Vladeta Jovovic *)

Formula

Comment from Vladeta Jovovic, Mar 15 2009: It is not difficult to prove that a(n) = A000088(n-1) - Sum_{k=1..n-1} a(k)*A002854(n-k), n>1, with a(1) =1, which is equivalent to the conjecture that the Euler transform of A158007(n) gives A007126(n+1) (see A158007).

O.g.f.: x*G(x)/(1+H(x)), where G(x) = 1+x+2*x^2+4*x^3+11*x^4+34*x^5+... = o.g.f for A000088 and H(x) = x+x^2+2*x^3+3*x^4+7*x^5+16*x^6+... = o.g.f for A002854. [Vladeta Jovovic, Mar 14 2009]