A004108 Number of n-node unlabeled connected graphs without endpoints. (Formerly M2910)

1, 1, 0, 1, 3, 11, 61, 507, 7442, 197772, 9808209, 902884343, 153723152913, 48443147912137, 28363697921914475, 30996525982586676021, 63502034385272108655525, 244852545421597419740767106, 1783161611489937453151313949442, 24603891216883233547700609793901996

Offset

0,5

Comments

Also number of n-node unlabeled connected mating graphs, cf. A006024 and A092430 (conjectured by Vladeta Jovovic, proved by G. Kilibarda). - Vladeta Jovovic, Oct 07 2004

References

F. Harary and E. Palmer, Graphical Enumeration, (1973), formula (8.7.11).

Goran Kilibarda, "Enumeration of unlabeled mating graphs", Belgrade, 2004, to be published.

R. W. Robinson, personal communication.

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 1..26 from R. W. Robinson)

David Cook II, Nested colourings of graphs, arXiv preprint arXiv:1306.0140 [math.CO], 2013.

Goran Kilibarda, Enumeration of Unlabeled Mating Graphs, Graphs and Combinatorics, Volume 23, Number 2 / April, 2007, pp. 183-199.

R. W. Robinson, Connected graphs without endpoints - computer printout

Eric Weisstein's World of Mathematics, Connected Graph.

Formula

Inverse Euler transform of A004110. - Andrew Howroyd, Sep 09 2018

Mathematica

terms = 19;
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
b[n_] := Sum[permcount[p]*2^edges[p]*Coefficient[Product[1 - x^p[[i]], {i, 1, Length[p]}], x, n - k]/k!, {k, 1, n}, {p, IntegerPartitions[k]}];
A004110 = Table[b[n], {n, 1, terms-1}];
Join[{1}, EULERi[A004110]] (* Jean-François Alcover, Jan 21 2019, after Andrew Howroyd *)

Crossrefs

Cf. A059166 (n-node connected labeled graphs without endpoints), A059167 (n-node labeled graphs without endpoints), A004110 (Euler Transform, n-node unlabeled graphs without endpoints).

Cf. A092430 (n-node labeled connected mating graphs).

See also A261919.

Cf. A342556, A342557.

Counts include those for distance-critical graphs, A349402.

Sequence in context: A024528 A368880 A273468 * A203007 A343774 A296321

Adjacent sequences: A004105 A004106 A004107 * A004109 A004110 A004111

Keyword

nonn

Author

N. J. A. Sloane

Extensions

a(0)=1 prepended by Andrew Howroyd, Sep 09 2018

Status

approved