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, 245935864212056913811498454, 1787577725208700551275529005084, 24637809253253259917745389824933448

Offset: 1

Author

Geoffrey Critzer, Oct 15 2012

Keywords

• nonn

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

Examples

			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
		

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

Crossrefs

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

Programs

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

PARI

{c=[1, 1, 2, 6, 21, 112, 853, 11117, 261080, 11716571, 1006700565, 164059830476, 50335907869219, 29003487462848061, 31397381142761241960, 63969560113225176176277, 245871831682084026519528568, 1787331725248899088890200576580, 24636021429399867655322650759681644];}
for(n=0,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 */

Python

from functools import lru_cache
from itertools import combinations
from fractions import Fraction
from math import prod, gcd, factorial, comb
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A216785(n):
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<>1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n)))
    @lru_cache(maxsize=None)
    def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
    @lru_cache(maxsize=None)
    def d(n): return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n
    return sum(d(i)*d(n-i) for i in range(1,n+1>>1)) + (0 if n&1 else comb(d(n>>1),2)) # Chai Wah Wu, Jul 03 2024

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.

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