|
| |
|
|
A216785
|
|
Number of unlabeled graphs on n nodes that have exactly two non-isomorphic 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
|
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, 18 Jul 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
|
| |
|
|
