A117356 -id:A117356 - cp's OEIS frontend

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

Franklin T. Adams-Watters, Mar 09 2006

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

			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).

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.

Cf. A000081, A117356, A363336, A363337.

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

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

{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 */

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

A117357 Number of rooted trees with total weight n, where the weight of a node at height k is k (with the root considered to be at level 1).

Original entry on oeis.org

0, 1, 0, 1, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 5, 7, 7, 11, 12, 16, 19, 25, 29, 38, 46, 59, 72, 91, 110, 141, 171, 214, 264, 331, 405, 509, 623, 777, 957, 1189, 1462, 1822, 2235, 2774, 3418, 4228, 5205, 6442, 7922, 9793, 12053, 14870, 18298, 22572, 27747, 34203

Offset: 0

Franklin T. Adams-Watters, Mar 09 2006

nonn

Equivalently, number of trees total weight n when the weight of each node is the size of its subtree. To get the equivalence, simply distribute the weights on each node one each to the node and each of its ancestors. - Franklin T. Adams-Watters, Oct 03 2009

			a(9) = 2; there is one tree with root at height 1 and 4 nodes at height 2 (1+4*2 = 9) and one with root at height 1, 1 node at height 2 and 2 nodes at height 3 (1+2+2*3 = 9).

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

Cf. A117356, A000081.

g:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g(i-k, i-k, k+1)+j-1, j)*g(n-i*j, i-1, k), j=0..n/i)))
    end:
a:= n-> g(n-1, n-1, 2):
seq(a(n), n=0..60);  # Alois P. Heinz, May 16 2013

g[n_, i_, k_] := g[n, i, k] = If[n==0, 1, If[i<1, 0, Sum[Binomial[g[i-k, i - k, k+1]+j-1, j]*g[n-i*j, i-1, k], {j, 0, n/i}]]]; a[n_] := g[n-1, n-1, 2]; Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Feb 21 2017, after Alois P. Heinz *)

If a(n) is the equivalent of this sequence with the root node considered to be at level k, then a(n) is the Euler transform of a(n) shifted right k places. To compute N terms, take k so that (k+1)*(k+2)/2 > N, approximate a(n) by 1 if n=k, 0 otherwise and apply this rule repeatedly. Formula from Christian G. Bower.

cp's OEIS Frontend

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).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula