|
%I #77 Jul 04 2024 04:01:19
%S 0,0,1,2,8,28,145,1022,12320,274785,12007355,1019030127,165091859656,
%T 50502058491413,29054157815353374,31426486309136268658,
%U 64001015806929213894372,245935864212056913811498454,1787577725208700551275529005084,24637809253253259917745389824933448
%N Number of unlabeled graphs on n nodes that have exactly two non-isomorphic components.
%C Stated more precisely: Number of unlabeled graphs on n nodes that have exactly two connected components and these components are not isomorphic (and nonempty).
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973, page 48.
%H David Broadhurst, <a href="/A216785/b216785.txt">Table of n, a(n) for n = 1..76</a>
%F 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.
%e 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
%e 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
%t 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 *)
%o (PARI) {c=[1, 1, 2, 6, 21, 112, 853, 11117, 261080, 11716571, 1006700565, 164059830476, 50335907869219, 29003487462848061, 31397381142761241960, 63969560113225176176277, 245871831682084026519528568, 1787331725248899088890200576580, 24636021429399867655322650759681644];}
%o 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 */
%o (Python)
%o from functools import lru_cache
%o from itertools import combinations
%o from fractions import Fraction
%o from math import prod, gcd, factorial, comb
%o from sympy import mobius, divisors
%o from sympy.utilities.iterables import partitions
%o def A216785(n):
%o @lru_cache(maxsize=None)
%o def b(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q>>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)))
%o @lru_cache(maxsize=None)
%o def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
%o @lru_cache(maxsize=None)
%o def d(n): return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n
%o 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
%Y Cf. A058915, A001349, A217955, A275165, A275166 (allows an empty component), A274934 (allows isomorphic components).
%K nonn
%O 1,4
%A _Geoffrey Critzer_, Oct 15 2012
%E 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.)
|
