

A216785


Number of unlabeled graphs on n nodes that have exactly two nonisomorphic components.


11



0, 0, 1, 2, 8, 28, 145, 1022, 12320, 274785, 12007355, 1019030127, 165091859656, 50502058491413, 29054157815353374, 31426486309136268658, 64001015806929213894372
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



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_]=1Product[1/(1x^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 JeanFranç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, (n1)\2, c[j]*c[nj])+if(n%2==0, c[n/2]*(c[n/2]1)/2)]


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



