login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A339836
Number of bicolored graphs on n unlabeled nodes such that every white node is adjacent to a black node.
4
1, 1, 3, 10, 47, 296, 2970, 49604, 1484277, 81494452, 8273126920, 1552510549440, 538647737513260, 346163021846858368, 413301431190875322768, 920040760819708654610560, 3832780109273882704828352620, 29989833030101321999992097828464, 442280129125813382230656891568680400
OFFSET
0,3
COMMENTS
The black nodes form a dominating set. For n > 0, a(n) is then the total number of indistinguishable dominating sets summed over distinct unlabeled graphs on n nodes.
LINKS
Eric Weisstein's World of Mathematics, Dominating 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)}
dom(u, v) = {prod(i=1, #u, 2^sum(j=1, #v, gcd(u[i], v[j]))-1)}
U(nb, nw)={my(s=0); forpart(u=nw, my(t=0); forpart(v=nb, t += permcount(v) * 2^edges(v) * dom(u, v)); s += t*permcount(u) * 2^edges(u)/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. A339832, A339834 (trees), A340021.
Sequence in context: A249479 A355154 A236410 * A105748 A277746 A140964
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Dec 19 2020
STATUS
approved