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

1, 1, 1, 2, 2, 3, 5, 6, 8, 12, 16, 22, 31, 41, 56, 78, 104, 142, 194, 260, 353, 478, 641, 864, 1164, 1560, 2095, 2810, 3757, 5028, 6722, 8966, 11963, 15945, 21223, 28244, 37551, 49871, 66210, 87829, 116411, 154222, 204162, 270084, 357117, 471881, 623146

Offset

0,4

Comments

Equivalently, number of forests of total weight n, when the roots are considered to be at height 1; so this is the Euler transform of A117357. - Franklin T. Adams-Watters, Oct 03 2009

Links

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

Formula

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

Example

a(3) = 2; there is one tree with 3 nodes at height 1 and one with 1 node at height 1 and 1 at height 2.

Maple

g:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<k, 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, n, 1):
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 < k, 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, n, 1];
a /@ Range[0, 60] (* Jean-François Alcover, Nov 05 2020, after Alois P. Heinz *)

Crossrefs

Cf. A000081, A115593, A117357.

Sequence in context: A032153 A309223 A116465 * A017819 A274148 A050044

Adjacent sequences: A117353 A117354 A117355 * A117357 A117358 A117359

Keyword

nonn

Author

Franklin T. Adams-Watters, Mar 09 2006

Status

approved