A006964 Number of directed rooted trees with n nodes. (Formerly M2994)

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,2

Comments

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

References

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

Links

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

Formula

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

Maple

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

Mathematica

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

Crossrefs

Cf. A038059.

Column k=3 of A242249.

Sequence in context: A059271 A345885 A014276 * A371616 A203507 A192662

Adjacent sequences: A006961 A006962 A006963 * A006965 A006966 A006967

Keyword

nonn,eigen

Author

Simon Plouffe

Extensions

Extended by Christian G. Bower, Apr 15 1998

Status

approved