login
A339832
Number of bicolored graphs on n unlabeled nodes such that black nodes are not adjacent to each other.
7
1, 2, 5, 14, 50, 230, 1543, 16252, 294007, 9598984, 577914329, 64384617634, 13264949930889, 5055918209734322, 3572106887472105263, 4692016570446185240464, 11496632576435936553085113, 52730955262459923752850296554, 454273406825238417871411598421653
OFFSET
0,2
COMMENTS
The black nodes form an independent vertex set. For n > 0, a(n) is then the total number of indistinguishable independent vertex sets summed over distinct unlabeled graphs on n nodes.
LINKS
Eric Weisstein's World of Mathematics, Independent Vertex Set
PROG
(PARI)
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
cross(u, v) = {sum(i=1, #u, sum(j=1, #v, gcd(u[i], v[j])))}
U(nb, nw)={my(s=0); forpart(v=nw, my(t=0); forpart(u=nb, t += permcount(u) * 2^cross(u, v)); s += t*permcount(v) * 2^edges(v)/nb!); s/nw!}
a(n) = {sum(k=0, n, U(k, n-k))}
CROSSREFS
A049312 counts bicolored graphs where adjacent nodes cannot have the same color.
A000666 counts bicolored graphs where adjacent nodes can have the same color.
Cf. A079491 (labeled case), A339830 (trees), A339836, A340021.
Sequence in context: A341360 A320954 A322725 * A245883 A115340 A298361
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Dec 19 2020
STATUS
approved