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

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

Author

Franklin T. Adams-Watters, Mar 09 2006

Keywords

• nonn

Comments

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

Examples

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

Links

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

Crossrefs

Cf. A117356, A000081.

Programs

Maple

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

Mathematica

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

Formula

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.