A004114 Number of trees with n nodes and 2-colored internal (non-leaf) nodes.

1, 1, 1, 2, 5, 12, 33, 98, 305, 1002, 3424, 12016, 43230, 158516, 590621, 2230450, 8521967, 32889238, 128064009, 502590642, 1986357307, 7900377892, 31602819524, 127076645038, 513419837168, 2083414420394, 8488377206876, 34712566540014, 142443837953632

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

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 = 0..500
• F. Harary, R. W. Robinson and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A, 20 (1975), 483-503. Errata: Vol. A 41 (1986), p. 325.
• Index entries for sequences related to trees

Crossrefs

Cf. A004113, A052316, A052317.

Programs

Mathematica

max = 28; etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[j]}]*b[n - j], {j, 1, n}]/n ]; b]; bb = etr[A004113]; A004113[n_] := If[n <= 1, n, 2*bb[n - 1]]; b[x_] := Sum[A004113[n] x^n, {n, 1, max}]; f[x_] := Sum[a[n] x^n, {n, 0, max}]; a[0] = a[1] = a[2] = 1; coes = CoefficientList[ Series[f[x] - (1 + b[x] - x*b[x] - b[x]^2/2 + b[x^2]/2), {x, 0, max}], x]; Table[a[n], {n, 0, max}] /. Solve[Thread[coes == 0]][[1]] (* Jean-François Alcover, Jan 29 2013, after Alois P. Heinz *)

Formula

G.f.: 1+B(x)-x*B(x)-B(x)^2/2+B(x^2)/2 where B(x) is g.f. of A004113. - Christian G. Bower, Dec 15 1999

a(n) ~ c * d^n / n^(5/2), where d = 4.49415643203339504537343052... (same as for A004113), c = 0.31497820931312537077... . - Vaclav Kotesovec, Sep 12 2014

Extensions

More terms, and new description from Christian G. Bower, Dec 15 1999