|
|
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, 245935864212056913811498454, 1787577725208700551275529005084, 24637809253253259917745389824933448
(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_]=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=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
@lru_cache(maxsize=None)
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)))
@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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|