A275165 Number of n-node graphs with two connected components.

1, 1, 2, 3, 9, 29, 142, 998, 12145, 273400, 11991377, 1018707920, 165078860715, 50500999728875, 29053989521340327, 31426435300576595334, 64000986599534312456052, 245935832697890955733422940, 1787577661113111145804012336114, 24637809007125076355873926288686728

Offset

0,3

Comments

"Component" means there are no edges from a node of one component to any node of the other component.

Each of the 2 components may be the empty graph with 0 nodes. That means the graph has only one "visible" component in these cases.

Each of the 2 components must be a connected graph (see A001349). (The empty graph has all properties and is a connected graph.)

The graphs of the components may be the same (=isomorphic).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..75

Formula

G.f.: [A(x)^2 + A(x^2)]/2 where A(x) is the o.g.f. for A001349.

a(n) = A275166(n) if n odd.

Example

a(4)=9 = 1*6 + 1*2 + 1*1 where 1*6=A001349(0)*A001349(4) counts graphs with an empty component and a component with 4 nodes, where 1*2 = A001349(1)*A001349(3) counts graphs with a component of 1 node and a component of 3 nodes, and where 1*1 = A001349(2)*A001349(2) counts graph with a component of 2 nodes and another component of 2 nodes (both components the same in that case).

Mathematica

terms = 20;
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!];
A[x_] = Join[{1}, EULERi[Array[a88, terms]]].(x^Range[0, terms]);
CoefficientList[(A[x]^2 + A[x^2])/2 + O[x]^terms, x] (* Jean-François Alcover, May 28 2019, after Andrew Howroyd in A001349 *)

Crossrefs

Cf. A216785, A001349, A275166, A274934 (no empty components).

Sequence in context: A153701 A176678 A277251 * A073950 A281270 A322752

Adjacent sequences: A275162 A275163 A275164 * A275166 A275167 A275168

Keyword

nonn

Author

R. J. Mathar, Jul 18 2016

Status

approved