|
%I #8 Jan 10 2021 02:13:56
%S 1,1,3,10,47,296,2970,49604,1484277,81494452,8273126920,1552510549440,
%T 538647737513260,346163021846858368,413301431190875322768,
%U 920040760819708654610560,3832780109273882704828352620,29989833030101321999992097828464,442280129125813382230656891568680400
%N Number of bicolored graphs on n unlabeled nodes such that every white node is adjacent to a black node.
%C 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.
%H Andrew Howroyd, <a href="/A339836/b339836.txt">Table of n, a(n) for n = 0..40</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DominatingSet.html">Dominating Set</a>
%o (PARI)
%o 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}
%o edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
%o dom(u, v) = {prod(i=1, #u, 2^sum(j=1, #v, gcd(u[i], v[j]))-1)}
%o 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!}
%o a(n)={sum(k=0, n, U(k, n-k))}
%Y A049312 counts bicolored graphs where adjacent nodes cannot have the same color.
%Y A000666 counts bicolored graphs where adjacent nodes can have the same color.
%Y Cf. A339832, A339834 (trees), A340021.
%K nonn
%O 0,3
%A _Andrew Howroyd_, Dec 19 2020
|
