A241839 Number of simple connected graphs on n nodes that are not regular.

0, 0, 1, 4, 19, 107, 849, 11100, 261058, 11716404, 1006700026, 164059811497, 50335907479783, 29003487412533265, 31397381139819043520, 63969560111526659139866, 245871831681641239553413008, 1787331725248249110678608976294, 24636021429399437942454151113206764

Offset

1,4

Links

Table of n, a(n) for n=1..19.

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs

T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.

Eric Weisstein's World of Mathematics, Regular Graph

Formula

a(n) = A001349(n) - A005177(n). - Andrew Howroyd, Nov 04 2017

Mathematica

A005177 = {1, 1, 1, 1, 2, 2, 5, 4, 17, 22, 167, 539, 18979, 389436, 50314796, 2942198440, 1698517036411};
terms = Length[A005177] - 1;
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]];
a88[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
A001349 = Join[{1}, EULERi[Array[a88, terms]]];
Rest[A001349 - A005177] (* Jean-François Alcover, Feb 23 2019, after Andrew Howroyd *)

Crossrefs

Cf. A002851, A006820, A006822.

Sequence in context: A249934 A174992 A182541 * A218183 A206227 A091643

Adjacent sequences: A241836 A241837 A241838 * A241840 A241841 A241842

Keyword

nonn

Author

Travis Hoppe and Anna Petrone, Apr 29 2014

Extensions

a(11)-a(16) from Andrew Howroyd, Nov 04 2017

Terms a(17) and beyond from Andrew Howroyd, May 21 2020

Status

approved