A339832
Number of bicolored graphs on n unlabeled nodes such that black nodes are not adjacent to each other.
Original entry on oeis.org
1, 2, 5, 14, 50, 230, 1543, 16252, 294007, 9598984, 577914329, 64384617634, 13264949930889, 5055918209734322, 3572106887472105263, 4692016570446185240464, 11496632576435936553085113, 52730955262459923752850296554, 454273406825238417871411598421653
Offset: 0
A049312 counts bicolored graphs where adjacent nodes cannot have the same color.
A000666 counts bicolored graphs where adjacent nodes can have the same color.
-
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))}
A339837
Number of bicolored trees on n unlabeled nodes such that black nodes are not adjacent to each other and every white node is adjacent to a black node.
Original entry on oeis.org
1, 1, 1, 2, 4, 8, 18, 44, 111, 296, 819, 2332, 6808, 20302, 61559, 189413, 590091, 1858187, 5906637, 18932016, 61130413, 198697205, 649706622, 2135958254, 7056831766, 23420011178, 78048740454, 261099605923, 876564670090, 2952491169904, 9975191222798
Offset: 0
a(2) = 1 because exactly one node must be colored black.
a(3) = 2 because the only tree is the path graph P_3. If the center node is colored black then neither of the ends can be colored black; otherwise both of the ends must be colored black. In total there are 2 possibilities.
There are 3 trees with 5 nodes:
o o
| |
o---o---o o---o---o---o---o o---o---o
| |
o o
These correspond respectively to 3, 3 and 2 solutions, so a(5) = 3 + 3 + 2 = 8.
-
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(u=v=w=[]); for(n=1, n, my(t1=EulerT(v), t2=EulerT(u+v)); u=concat([1], EulerT(v+w)); v=concat([0], t2-t1); w=concat([1], t1)); my(g=x*Ser(u+v), gu=x*Ser(u), gw=x*Ser(w)); Vec(1 + g + (subst(g,x,x^2) - subst(gu,x,x^2) - g^2 - 2*gu*gw + gu^2)/2)}
A339836
Number of bicolored graphs on n unlabeled nodes such that every white node is adjacent to a black node.
Original entry on oeis.org
1, 1, 3, 10, 47, 296, 2970, 49604, 1484277, 81494452, 8273126920, 1552510549440, 538647737513260, 346163021846858368, 413301431190875322768, 920040760819708654610560, 3832780109273882704828352620, 29989833030101321999992097828464, 442280129125813382230656891568680400
Offset: 0
A049312 counts bicolored graphs where adjacent nodes cannot have the same color.
A000666 counts bicolored graphs where adjacent nodes can have the same color.
-
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))}
Showing 1-3 of 3 results.
Comments