A243243 Number of unlabeled, connected graphs on n vertices with at least one subgraph isomorphic to a C_4, where C_4 is the cycle graph on four vertices.

0, 0, 0, 3, 13, 93, 796, 10931, 260340, 11713182, 1006682063, 164059710255, 50335906936959, 29003487454251217, 31397381142667479256, 63969560113223974443840, 245871831682084008526845525, 1787331725248899088577102145274, 24636021429399867655316345340289103

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, Square-Free Graph

Formula

a(n) = A001349(n) - A077269(n).

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]];
a88[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
A001349 = EULERi[Array[a88, terms]];
A006786 = {1, 2, 4, 8, 18, 44, 117, 351, 1230, 5069, 25181, 152045, 1116403, 9899865, 104980369, 1318017549, 19427531763, 333964672216, 6660282066936};
A077269 = EULERi[A006786];
A001349 - A077269 (* Jean-François Alcover, Feb 15 2019, after Andrew Howroyd in A001349 and A077269 *)

Crossrefs

Cf. A001349, A077269.

Sequence in context: A034513 A257661 A292501 * A274052 A305207 A369197

Adjacent sequences: A243240 A243241 A243242 * A243244 A243245 A243246

Keyword

nonn

Author

Travis Hoppe and Anna Petrone, Jun 01 2014

Extensions

a(11)-a(17) using formula from Falk Hüffner, Jan 15 2016

a(18)-a(19) from Jean-François Alcover, Feb 15 2019 using Andrew Howroyd's code.

Status

approved