|
%I #24 May 28 2019 08:13:13
%S 1,1,2,3,9,29,142,998,12145,273400,11991377,1018707920,165078860715,
%T 50500999728875,29053989521340327,31426435300576595334,
%U 64000986599534312456052,245935832697890955733422940,1787577661113111145804012336114,24637809007125076355873926288686728
%N Number of n-node graphs with two connected components.
%C "Component" means there are no edges from a node of one component to any node of the other component.
%C 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.
%C Each of the 2 components must be a connected graph (see A001349). (The empty graph has all properties and is a connected graph.)
%C The graphs of the components may be the same (=isomorphic).
%H Alois P. Heinz, <a href="/A275165/b275165.txt">Table of n, a(n) for n = 0..75</a>
%F G.f.: [A(x)^2 + A(x^2)]/2 where A(x) is the o.g.f. for A001349.
%F a(n) = A275166(n) if n odd.
%e 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).
%t terms = 20;
%t mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
%t 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]];
%t 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];
%t edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] +
%t Total[Quotient[v, 2]];
%t a88[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
%t A[x_] = Join[{1}, EULERi[Array[a88, terms]]].(x^Range[0, terms]);
%t CoefficientList[(A[x]^2 + A[x^2])/2 + O[x]^terms, x] (* _Jean-François Alcover_, May 28 2019, after _Andrew Howroyd_ in A001349 *)
%Y Cf. A216785, A001349, A275166, A274934 (no empty components).
%K nonn
%O 0,3
%A _R. J. Mathar_, Jul 18 2016
|
