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