|
%I #66 Mar 03 2024 09:30:54
%S 0,0,1,2,8,28,145,1022,12320,274785,12007355,1019030127,165091859656,
%T 50502058491413,29054157815353374,31426486309136268658,
%U 64001015806929213894372
%N Number of unlabeled graphs on n nodes that have exactly two non-isomorphic components.
%C Stated more precisely: Number of unlabeled graphs on n nodes that have exactly two connected components and these components are not isomorphic (and nonempty).
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973, page 48.
%H David Broadhurst, <a href="/A216785/b216785.txt">Table of n, a(n) for n = 1..76</a>
%F O.g.f.: A(x)^2/2 - A(x^2)/2 where A(x) is the o.g.f. for A001349 after setting A001349(0)=0.
%e a(4)=2 = 1*2 where 1*2=A001349(1)*A001349(3) counts graphs with a component of 1 node and a component with 3 nodes. There is no contribution with a component of 2 nodes and another component of 2 nodes because A001349(2)=1 means these components would be isomorphic. - _R. J. Mathar_, Jul 18 2016
%e a(5)=8 = 1*6 + 1*2 where 1*6=A001349(1)*A001349(4) counts graphs with a component of 1 node and a component with 4 nodes, and where 1*2 = A001349(2)*A001349(3) counts graphs with a component of 2 nodes and a component of 3 nodes. - _R. J. Mathar_, Jul 18 2016
%t Needs["Combinatorica`"]; max=25; A000088=Table[NumberOfGraphs[n], {n, 0, max}]; f[x_]=1-Product[1/(1-x^k)^a[k], {k, 1, max}]; a[0]=a[1]=a[2]=1; coes=CoefficientList[Series[f[x], {x, 0, max}], x]; sol=First[Solve[Thread[Rest[coes+A000088]==0]]]; cg=Table[a[n], {n, 1, max}]/.sol; Take[CoefficientList[CycleIndex[AlternatingGroup[2], s]-CycleIndex[SymmetricGroup[2], s]/.Table[s[j]->Table[Sum[cg[[i]] x^(k*i), {i, 1, max}], {k, 1, max}][[j]], {j, 1, 3}], x], {4, max}] (* after code given by _Jean-François Alcover_ in A001349 *)
%o (PARI) {c=[1, 1, 2, 6, 21, 112, 853, 11117, 261080, 11716571, 1006700565, 164059830476, 50335907869219, 29003487462848061, 31397381142761241960, 63969560113225176176277, 245871831682084026519528568, 1787331725248899088890200576580, 24636021429399867655322650759681644];}
%o for(n=3,19,print([n,sum(j=1,(n-1)\2,c[j]*c[n-j])+if(n%2==0,c[n/2]*(c[n/2]-1)/2)]
%o )); /* _David Broadhurst_, Jul 18 2016 */
%Y Cf. A058915, A001349, A217955, A275165, A275166 (allows an empty component), A274934 (allows isomorphic components).
%K nonn
%O 1,4
%A _Geoffrey Critzer_, Oct 15 2012
%E Two zeros prepended (offset changed), formula updated, and entries corrected by _R. J. Mathar_, _N. J. A. Sloane_, Jul 18 2016. (Thanks to _Allan C. Wechsler_ for pointing out that all the entries above a(19) were wrong.)
|
