A216785 Number of unlabeled graphs on n nodes that have exactly two non-isomorphic components.

0, 0, 1, 2, 8, 28, 145, 1022, 12320, 274785, 12007355, 1019030127, 165091859656, 50502058491413, 29054157815353374, 31426486309136268658, 64001015806929213894372

Offset

1,4

Comments

Stated more precisely: Number of unlabeled graphs on n nodes that have exactly two connected components and these components are not isomorphic (and nonempty).

References

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973, page 48.

Links

David Broadhurst, Table of n, a(n) for n = 1..76

Formula

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.

Example

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
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

Mathematica

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 *)

Prog

(PARI) {c=[1, 1, 2, 6, 21, 112, 853, 11117, 261080, 11716571, 1006700565, 164059830476, 50335907869219, 29003487462848061, 31397381142761241960, 63969560113225176176277, 245871831682084026519528568, 1787331725248899088890200576580, 24636021429399867655322650759681644]; }
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)]
)); /* David Broadhurst, Jul 18 2016 */

Crossrefs

Cf. A058915, A001349, A217955, A275165, A275166 (allows an empty component), A274934 (allows isomorphic components).

Sequence in context: A150732 A225689 A330211 * A261559 A061230 A241627

Adjacent sequences: A216782 A216783 A216784 * A216786 A216787 A216788

Keyword

nonn

Author

Geoffrey Critzer, Oct 15 2012

Extensions

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.)

Status

approved