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

%I #15 Nov 05 2020 07:44:05

%S 1,1,1,2,2,3,5,6,8,12,16,22,31,41,56,78,104,142,194,260,353,478,641,

%T 864,1164,1560,2095,2810,3757,5028,6722,8966,11963,15945,21223,28244,

%U 37551,49871,66210,87829,116411,154222,204162,270084,357117,471881,623146

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

%C 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

%H Alois P. Heinz, <a href="/A117356/b117356.txt">Table of n, a(n) for n = 0..500</a>

%F 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_.

%e 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.

%p g:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<k, 0, add(

%p binomial(g(i-k, i-k, k+1)+j-1, j)*g(n-i*j, i-1, k), j=0..n/i)))

%p end:

%p a:= n-> g(n, n, 1):

%p seq(a(n), n=0..60); # _Alois P. Heinz_, May 16 2013

%t 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}]]];

%t a[n_] := g[n, n, 1];

%t a /@ Range[0, 60] (* _Jean-François Alcover_, Nov 05 2020, after _Alois P. Heinz_ *)

%Y Cf. A000081, A115593, A117357.

%K nonn

%O 0,4

%A _Franklin T. Adams-Watters_, Mar 09 2006