A271878 -id:A271878 - cp's OEIS frontend

A038055 Number of n-node rooted trees with nodes of 2 colors.

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

Christian G. Bower, Jan 04 1999

Alois P. Heinz, Table of n, a(n) for n = 1..1000
L. Foissy, Algebraic structures on typed decorated rooted trees, arXiv:1811.07572 [math.RA] (2018).
R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603.00077 [math.CO] (2016), Table 3.
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000081, A038056-A038062, A271878 (multisets).

Cf. A245870.

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

Shifts left and halves under Euler transform.
a(n) = 2*A000151(n).
a(n) ~ c * d^n / n^(3/2), where d = A245870 = 5.646542616232949712892713516..., c = 0.41572319484583484264330698410170337587070758092051645875080558178621559423... . - Vaclav Kotesovec, Sep 11 2014, updated Dec 26 2020

A271879 Triangle T(n,t) by rows: The number of rooted forests with n 3-colored nodes and t rooted trees.

Original entry on oeis.org

3, 9, 6, 45, 27, 10, 246, 180, 54, 15, 1485, 1143, 405, 90, 21, 9432, 7704, 2856, 720, 135, 28, 62625, 52731, 20682, 5385, 1125, 189, 36, 428319, 369969, 150282, 40914, 8730, 1620, 252, 45, 3000393, 2638332, 1104702, 309510, 68400, 12891, 2205, 324, 55

Offset: 1

R. J. Mathar, Apr 16 2016

See eq. (27) of the reference for a recurrence.

			3 ;
9 6 ;
45 27 10;
246 180 54 15;
1485 1143 405 90 21;
9432 7704 2856 720 135 28;
62625 52731 20682 5385 1125 189 36;
428319 369969 150282 40914 8730 1620 252 45;
3000393 2638332 1104702 309510 68400 12891 2205 324 55;
21410436 19097802 8183943 2353989 531702 103140 17868 2880 405 66;
155106693 139921470 61122222 17954262 4140105 816858 145134 23661 3645 495 78;
1137703869 1035882315 459695791 137490273 32241834 6466053 1164978 194382 30270 4500 594 91 ;
8432624850 7737370857 3479520051 1056731244 251493255 51104574 9331833 1576062 250884 37695 5445 702 105 ;

Alois P. Heinz, Rows n = 1..141, flattened
R. J. Mathar, Topologically distinct sets of non-intersecting circles in the plane, arXiv:1603:00077 [math.CO] (2016), Table 4.

Cf. A033185 (1-colored nodes), A038059 (column k=1), A006964 (row sums), A271878 (2-colored nodes).

g:= proc(n) option remember; `if`(n<2, 3*n, (add(add(d*g(d),
       d=numtheory[divisors](j))*g(n-j), j=1..n-1))/(n-1))
    end:
b:= proc(n, i, p) option remember; `if`(p>n, 0, `if`(n=0, 1,
      `if`(min(i, p)<1, 0, add(b(n-i*j, i-1, p-j)*
       binomial(g(i)+j-1, j), j=0..min(n/i, p)))))
    end:
T:= (n, k)-> b(n$2, k):
seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Apr 13 2017

g[n_] := g[n] = If[n < 2, 3*n, (Sum[Sum[d*g[d], {d, Divisors[j]}]*g[n - j], {j, 1, n - 1}])/(n - 1)];
b[n_, i_, p_] := b[n, i, p] = If[p > n, 0, If[n == 0, 1, If[Min[i, p] < 1, 0, Sum[b[n - i*j, i - 1, p - j]*Binomial[g[i] + j - 1, j], {j, 0, Min[n/i, p]}]]]];
T[n_, k_] :=  b[n, n, k];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Nov 10 2017, after Alois P. Heinz *)

cp's OEIS Frontend

A038055 Number of n-node rooted trees with nodes of 2 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula