A038055
Number of n-node rooted trees with nodes of 2 colors.
Original entry on oeis.org
2, 4, 14, 52, 214, 916, 4116, 18996, 89894, 433196, 2119904, 10503612, 52594476, 265713532, 1352796790, 6933598208, 35747017596, 185260197772, 964585369012, 5043220350012, 26467146038744, 139375369621960, 736229024863276, 3900074570513316, 20714056652990194
Offset: 1
-
spec := [N, {N=Prod(bead,Set(N)), bead=Union(R,B), R=Atom, B=Atom}]; [seq(combstruct[count](spec, size=n), n=1..40)];
# second Maple program:
with(numtheory):
a:= proc(n) option remember; `if`(n<2, 2*n, (add(add(d*
a(d), d=divisors(j))*a(n-j), j=1..n-1))/(n-1))
end:
seq(a(n), n=1..30); # Alois P. Heinz, May 11 2014
-
a[n_] := a[n] = If[n<2, 2*n, (Sum[Sum[d*a[d], {d, Divisors[j]}]*a[n-j], {j, 1, n-1}])/(n-1)]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Feb 25 2015, after Alois P. Heinz *)
a[1] = 2; a[n_] := a[n] = Sum[k a[k] a[n - m k]/(n-1), {k, n}, {m, (n-1)/k}]; Table[a[n], {n, 30}] (* Vladimir Reshetnikov, Aug 12 2016 *)
-
seq(N) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 2/n * sum(i=1, n, sumdiv(i, d, d*A[d]) * A[n-i+1] ) ); 2*A} \\ Andrew Howroyd, May 12 2018
A294783
Number of trees with n bicolored nodes and f nodes of the first color. Triangle T(n,f) read by rows, 0<=f<=n.
Original entry on oeis.org
1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 2, 4, 6, 4, 2, 3, 9, 15, 15, 9, 3, 6, 20, 43, 51, 43, 20, 6, 11, 48, 116, 175, 175, 116, 48, 11, 23, 115, 329, 573, 698, 573, 329, 115, 23, 47, 286, 918, 1866, 2626, 2626, 1866, 918, 286, 47, 106, 719, 2609, 5978, 9656, 11241, 9656, 5978, 2609, 719, 106, 235, 1842
Offset: 0
The triangle starts
1;
1, 1;
1, 1, 1;
1, 2, 2, 1;
2, 4, 6, 4, 2;
3, 9, 15, 15, 9, 3;
6, 20, 43, 51, 43, 20, 6;
11, 48, 116, 175, 175, 116, 48, 11;
23, 115, 329, 573, 698, 573, 329, 115, 23;
47, 286, 918, 1866, 2626, 2626, 1866, 918, 286, 47;
106, 719,2609, 5978, 9656,11241, 9656,5978,2609,719,106;
235,1842,
-
R(n, y)={my(v=vector(n)); v[1]=1; for(k=1, n-1, my(p=(1+y)*v[k]); my(q=Vec(prod(j=0, poldegree(p,y), (1/(1-x*y^j) + O(x*x^(n\k)))^polcoeff(p,j)))); v=vector(n, j, v[j] + sum(i=1, (j-1)\k, v[j-i*k] * q[i+1]))); v;}
M(n)={my(B=(1+y)*x*Ser(R(n,y))); 1 + B - (B^2 - substvec(B, [x,y], [x^2,y^2]))/2}
{ my(A=M(10)); for(n=0, #A-1, print(Vecrev(polcoeff(A, n)))) } \\ Andrew Howroyd, May 12 2018
A339830
Number of bicolored trees on n unlabeled nodes such that black nodes are not adjacent to each other.
Original entry on oeis.org
1, 2, 2, 4, 10, 26, 75, 234, 768, 2647, 9466, 34818, 131149, 503640, 1965552, 7777081, 31138051, 125961762, 514189976, 2115922969, 8769932062, 36584593158, 153510347137, 647564907923, 2744951303121, 11687358605310, 49965976656637, 214423520420723, 923399052307921
Offset: 0
a(2) = 2 because at most one node can be colored black.
a(3) = 4 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 zero, one or both of the ends can be colored black. In total there are 4 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 11, 9 and 6 bicolored trees (with black nodes not adjacent), so a(5) = 11 + 9 + 6 = 26.
-
EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(u=v=[1]); for(n=2, n, my(t=concat([1], EulerT(v))); v=concat([1], EulerT(u+v)); u=t); my(g=x*Ser(u+v), gu=x*Ser(u)); Vec(1 + g + (subst(g,x,x^2) - subst(gu,x,x^2) - g^2 + gu^2)/2)}
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)}
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)}
Showing 1-5 of 5 results.
Comments