A115593 Number of forests of rooted trees with total weight n, where a node at height k has weight 2^k (with root considered to be at height 0).

1, 1, 1, 2, 2, 3, 4, 6, 7, 10, 13, 17, 22, 29, 38, 50, 64, 82, 107, 136, 175, 224, 288, 363, 465, 587, 748, 942, 1196, 1503, 1902, 2385, 3004, 3765, 4729, 5911, 7406, 9246, 11549, 14395, 17941, 22326, 27767, 34501, 42821, 53134, 65828, 81546, 100871, 124783

Offset

0,4

Comments

The sequence b(2n)=0, b(2n+1)=a(n) is the number of trees of weight n.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..5000

Hartosh Singh Bal, Combinatorics of a Class of Completely Additive Arithmetic Functions, arXiv:2308.00455 [math.CO], 2023.

Formula

Euler transform of b(n), where b(2n+1) = a(n) and b(2n) = 0.

From Paul D. Hanna, Oct 26 2011: (Start)

G.f. satisfies: A(x) = exp( Sum_{n>=1} A(x^(2*n)) * x^n/n ).

G.f. satisfies: A(x)*A(-x) = A(x^2). (End)

Let b(n) = a(n-1) for n>=1, then sum(n>=1, b(n)*x^n ) = x / prod(n>=1, (1-x^(2*n-1))^b(n) ); compare to A000081, A004111, and A073075. - Joerg Arndt, Mar 04 2015

a(0) = 1; a(n) = (1/n) * Sum_{k=1..n} ( Sum_{d|k and d is odd} d * a(floor(d/2)) ) * a(n-k). - Seiichi Manyama, May 31 2023

Example

a(3) = 2; one forest with 3 single-node trees and one with a single two-node tree (root node has weight 1, other node has weight 2).

Maple

with(numtheory):
b:= proc(n) local r; `if`(irem(n, 2, 'r')=0, 0, a(r)) end:
a:= proc(n) option remember; `if`(n=0, 1,
       add(add(d*b(d), d=divisors(j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, May 16 2013

Mathematica

b[n_] := b[n] = If[{q, r} = QuotientRemainder[n, 2]; r == 0, 0, a[q]]; a[n_] := a[n] = If[n == 0, 1, Sum[Sum[d*b[d], {d, Divisors[j]}]*a[n-j], {j, 1, n}]/n]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 23 2015, after Alois P. Heinz *)

Prog

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

Crossrefs

Cf. A000081, A117356, A363336, A363337.

Sequence in context: A039883 A024186 A239833 * A274312 A238861 A309212

Adjacent sequences: A115590 A115591 A115592 * A115594 A115595 A115596

Keyword

easy,nonn

Author

Franklin T. Adams-Watters, Mar 09 2006

Status

approved