A029856 Number of rooted trees with 2-colored leaves.

2, 2, 5, 13, 37, 108, 332, 1042, 3360, 11019, 36722, 123875, 422449, 1453553, 5040816, 17599468, 61814275, 218252584, 774226549, 2758043727, 9862357697, 35387662266, 127374191687, 459783039109, 1664042970924, 6037070913558, 21951214425140, 79981665585029

Offset

1,1

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 768

N. J. A. Sloane, Transforms

Index entries for sequences related to rooted trees

Formula

Shifts left under Euler transform.

G.f. satisfies: A(x) = x + x*exp( Sum_{n>=1} A(x^n)/n ). - Paul D. Hanna, Oct 19 2005

a(n) ~ c * d^n / n^(3/2), where d = 3.848442876944251389076286931217197... and c = 0.48335853985605895591573724406549734... - Vaclav Kotesovec, Mar 29 2014

Maple

A:= proc(n) option remember; if n=0 then 0 else convert(series(x+x* exp(sum(subs(x=x^i, A(n-1))/i, i=1..n-1)), x=0, n+1), polynom) fi end; a:= n-> coeff(A(n), x, n): seq(a(n), n=1..25); # Alois P. Heinz, Aug 22 2008
# second Maple program:
with(numtheory): a:= proc(n) option remember; local d, j; if n<=1 then 2*n else (add(d*a(d), d=divisors(n-1)) +add(add(d*a(d), d=divisors(j)) *a(n-j), j=1..n-2))/ (n-1) fi end: seq(a(n), n=1..25); # Alois P. Heinz, Sep 06 2008

Mathematica

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

Prog

(PARI) {a(n)=local(A=x+x*O(x^n)); for(i=1, n, A=x+x*exp(sum(m=1, n, subst(A, x, x^m)/m))); polcoeff(A, n, x)} \\ Paul D. Hanna, Oct 19 2005

Crossrefs

Essentially the same as A036249.

Cf. A000081, A029857, A038049.

Sequence in context: A078413 A019083 A355863 * A072898 A032290 A032201

Adjacent sequences: A029853 A029854 A029855 * A029857 A029858 A029859

Keyword

nonn,easy,eigen

Author

Christian G. Bower

Status

approved