Weighted trees

[Christian G. Bower]

> The hard case is to give each node at level k weight k.
> If we take the root level to be level 1, we get the following
> number of trees (these are hand-calculated, so there might be mistakes):
 
> 1,0,1,0,1,1,1,1,2,2,3,3,4,5,7,7
 
> The Euler transform of this is the number of trees taking
> the root to be at level 0:
 
> 1,1,1,2,2,3,5,6,8,12,16,22,31,41,56,78,104
 
> (the offset here is zero).  This sequence was mechanically
> calculated from the previous one.
 
> (1) Can somebody verify these?
> (2) ... extend them?
> (3) Is there a fairly easy way to calculate them?
 
> Note that neither is in the OEIS (assuming I have calculated them
correctly).

Let a<k>(n) be the number of rooted trees taking root to be level k.

Then a<k>(n) is Euler transform of a<k+1>(n) shifted right k places.

Let us take a<k>(n) to be the sequence with a<k>(k) = 1 and all other 0.
This is accurate for n=0 to 2k so this is good enough to calculate
a<0>(n) for n = 0 to 2k.  Actually it's a lot better than that.

So we take a<k-1>(n) as Euler a<k>(n) shifted right k-1 places.
Keep repeating until we reach a<0>(n).

We only need to invoke a<k>(n) to calculate a<0>(n) for a particular n
if one of the rooted trees has height at least n.  The lighted rooted
tree of height n sticks straight up with weight tri(n) = n*(n+1)/2.
Thus if n=100, k=13 is enough.

Example from k=5.

All sequences start at 0:

a<5>(n) 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
(only accurate to n=10)
a<4>(n) 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
(accurate to n=14)
a<3>(n) 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1
(accurate to n=17)
a<2>(n) 0 0 1 0 0 1 0 0 1 1 0 1 1 1 2 1 2 3 2 3
(accurate to n=19)
a<1>(n) 0 1 0 1 0 1 1 1 1 2 2 3 3 4 5 7 7 11 12 16
(accurate to n=20)
a<0>(n) 1 1 1 2 2 3 5 6 8 12 16 22 31 41 56 78 104 142 194 260
(accurate to n=20)

PS

If you'll excuse my retentiveness, it would be nice to call
trees: trees and rooted trees: rooted trees since both are in the
EIS in abundance and they are not the same thing.