login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 26 14:18 EST 2021. Contains 341632 sequences. (Running on oeis4.)