A339832 Number of bicolored graphs on n unlabeled nodes such that black nodes are not adjacent to each other.

1, 2, 5, 14, 50, 230, 1543, 16252, 294007, 9598984, 577914329, 64384617634, 13264949930889, 5055918209734322, 3572106887472105263, 4692016570446185240464, 11496632576435936553085113, 52730955262459923752850296554, 454273406825238417871411598421653

Offset: 0

Author

Andrew Howroyd, Dec 19 2020

Keywords

• nonn

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

• Andrew Howroyd, Table of n, a(n) for n = 0..40
• Eric Weisstein's World of Mathematics, Independent Vertex Set

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.

Programs

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