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))}
A339834
Number of bicolored trees on n unlabeled nodes such that every white node is adjacent to a black node.
Original entry on oeis.org
1, 1, 2, 4, 11, 29, 91, 299, 1057, 3884, 14883, 58508, 235771, 967790, 4037807, 17074475, 73058753, 315803342, 1377445726, 6056134719, 26817483095, 119516734167, 535751271345, 2414304071965, 10932421750492, 49723583969029, 227079111492652, 1040939109111200, 4788357522831785
Offset: 0
a(2) = 2 because at most one node can be colored white.
a(3) = 4 because the only tree is the path graph P_3. If the center node is colored white then both of the ends must be colored black; otherwise zero, one or both of the ends can be colored black. In total there are 4 possibilities.
-
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(u+v+w)); v=concat([0], t2-t1); w=concat([1], t1)); my(g=x*Ser(u+v), guw=x^2*Ser(u)*Ser(w)); Vec(1 + g + (subst(g,x,x^2) - g^2 - 2*guw)/2)}
A340021
Number of bicolored graphs 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, 2, 5, 16, 66, 407, 3948, 66781, 2057140, 117820559, 12562407832, 2488441442819, 915216371901462, 625792587599236833, 797474948692631218674, 1899724021357155410243835, 8486672841492724213636009230, 71324140440429733888694354552551, 1131126439181050621704917376323373818
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_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
dom[u_, v_] := Product[2^Sum[GCD[u[[i]], v[[j]]], {j, 1, Length[v]}] - 1, {i, 1, Length[u]}];
U[nb_, nw_] := Module[{s = 0}, Do[t = 0; Do[t += permcount[v]*dom[u, v], {v, IntegerPartitions[nb]}]; s += t*permcount[u]*2^edges[u]/nb!, {u, IntegerPartitions[nw]}]; s/nw!];
a[n_] := Sum[U[k, n - k], {k, 0, n}];
Array[a, 20] (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)
-
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) * 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