login
Number of forests of rooted trees where n dollars are spent and an n-node tree costs 2n-1 dollars.
2

%I #14 Feb 19 2016 06:40:39

%S 1,1,2,2,4,5,9,11,21,28,50,68,123,173,310,441,789,1147,2044,2999,5351,

%T 7938,14143,21138,37686,56729,101144,153085,273077,415407,741301,

%U 1132373,2021831,3100128,5537782,8519076,15225373,23491413,42003748,64979069,116239502

%N Number of forests of rooted trees where n dollars are spent and an n-node tree costs 2n-1 dollars.

%H Alois P. Heinz, <a href="/A038000/b038000.txt">Table of n, a(n) for n = 1..1000</a>

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%F EULER transform of {c(x)} where {c(x)} has g.f. B(x^2)/x = x+x^3+2*x^5+4*x^7+9*x^9+... and B(x) = x+x^2+2*x^3+4*x^4+9*x^5+... is g.f. for A000081.

%p with(numtheory):

%p b:= proc(n) option remember; local d, j; `if`(n<=1, n,

%p (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))

%p end:

%p c:= proc(n) local r; `if`(irem(n, 2, 'r')=0, 0, b(r+1)) end:

%p a:= proc(n) option remember; `if`(n=0, 1,

%p add(add(d*c(d), d=divisors(j))*a(n-j), j=1..n)/n)

%p end:

%p seq(a(n), n=1..50); # _Alois P. Heinz_, May 16 2013

%t b[n_] := b[n] = If[n <= 1, n, (Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}])/(n-1)]; c[n_] := If[Mod[n, 2]==0, 0, b[n/2 // Ceiling]]; a[n_] := a[n] = If[n==0, 1, Sum[Sum[d*c[d], {d, Divisors[j]}]*a[n-j], {j, 1, n}]/n]; Table[a[n], {n, 1, 50}] (* _Jean-François Alcover_, Feb 19 2016, after _Alois P. Heinz_ *)

%K nonn,easy

%O 1,3

%A _Christian G. Bower_