A038059 -id:A038059 - cp's OEIS frontend

A006964 Number of directed rooted trees with n nodes.

1, 3, 15, 82, 495, 3144, 20875, 142773, 1000131, 7136812, 51702231, 379234623, 2810874950, 21020047557, 158398829121, 1201617201230, 9169060501023, 70329406653879, 541949364313821, 4193569906262874, 32571403998781956, 253842927519362734, 1984442128649393178

Offset: 1

Simon Plouffe

Also rooted trees with n nodes and 3-colored non-root nodes. - Christian G. Bower, Apr 15 1998

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..500
Loïc Foissy, Algebraic structures on typed decorated rooted trees, arXiv:1811.07572 [math.RA], 2018.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 439
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Mathh
. Québec, Vol. 16, No. 1 (1992) pp. 53-80.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A038059.

Column k=3 of A242249.

with(numtheory): a:= proc(n) option remember; `if`(n<2, n, (add(add(d*a(d), d=divisors(j)) *a(n-j)*3, j=1..n-1))/(n-1)) end: seq(a(n), n=1..30); # Alois P. Heinz, Sep 06 2008

a[n_] := a[n] = If[n<2, n, (Sum[Sum[d*a[d], {d, Divisors[j]}]*a[n-j]*3, {j, 1, n-1}])/(n-1)]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Mar 30 2015, after Alois P. Heinz *)

a(n+1) has g.f.: Product_{n>=1} (1 - x^3*a(n))^-1.
a(n) ~ c * d^n / n^(3/2), where d = 8.356026879295995368276069578708912..., c = 0.13645899548680457355557420025756... . - Vaclav Kotesovec, Aug 20 2014
G.f. A(x) satisfies: A(x) = x*exp(3*Sum_{k>=1} A(x^k)/k). - Ilya Gutkovskiy, Mar 19 2018

Extended by Christian G. Bower, Apr 15 1998

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 *)

A339643 Number of rooted trees with n nodes colored using exactly 3 colors.

Original entry on oeis.org

0, 0, 9, 102, 870, 6744, 50421, 371676, 2731569, 20113005, 148752507, 1106207331, 8274878880, 62263100994, 471138360426, 3584051515209, 27399942354822, 210432444531798, 1622954350900455, 12565580096217270, 97634810663895132, 761110656740387865, 5951117699678438271

Offset: 1

Andrew Howroyd, Dec 11 2020

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..500

Column 3 of A141610.

Cf. A000081, A000151, A006964, A038055, A038059, A339642.

b:= proc(n, k) option remember; `if`(n<2, k*n, (add(add(b(d, k)*
      d, d=numtheory[divisors](j))*b(n-j, k), j=1..n-1))/(n-1))
    end:
a:= n-> b(n, 3)-3*b(n, 2)+3*b(n, 1):
seq(a(n), n=1..23);  # Alois P. Heinz, Dec 11 2020

b[n_, k_] := b[n, k] = If[n < 2, k*n, (Sum[Sum[b[d, k]*d, {d, Divisors[j]}]*b[n - j, k], {j, 1, n - 1}])/(n - 1)];
a[n_] := b[n, 3] - 3 b[n, 2] + 3 b[n, 1];
Array[a, 23] (* Jean-François Alcover, Jan 04 2021, after Alois P. Heinz *)

\\ See A141610 for U(N,m)
seq(n)={U(n,3) - 3*U(n,2) + 3*U(n,1)}

a(n) = A038059(n) - 3*A038055(n) + 3*A000081(n).

a(n) = 3*(A006964(n) - 2*A000151(n) + A000081(n)).

A038060 Number of trees with 3-colored nodes.

Original entry on oeis.org

1, 3, 6, 18, 75, 342, 1773, 9894, 58596, 362061, 2314119, 15185223, 101830986, 695253993, 4819762446, 33851833506, 240472935735, 1725315714729, 12487872432924, 91097741283408, 669227023979088, 4947500029023540, 36786363204267282, 274949933519917908

Offset: 0

Christian G. Bower, Jan 04 1999

nonn

Index entries for sequences related to trees

Cf. A000055, A038055-A038062.

Equals 3 * A006965(n).

b[n_] := b[n] = If[n < 2, 3n, (Sum[Sum[b[d] d, {d, Divisors[j]}] b[n - j], {j, 1, n - 1}])/(n - 1)];
a[n_] := If[n == 0, 1, b[n] - (Sum[b[k] b[n - k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2];
a /@ Range[0, 25] (* Jean-François Alcover, Nov 01 2020, after Alois P. Heinz in A006965 *)

G.f.: B(x) - B^2(x)/2 + B(x^2)/2, where B(x) is g.f. for A038059.

cp's OEIS Frontend

A006964 Number of directed rooted trees with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A339643 Number of rooted trees with n nodes colored using exactly 3 colors.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A038060 Number of trees with 3-colored nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula