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
Examples
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).
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.
Programs
-
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 *) -
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 */
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
Comments