A384938 Number for rooted ordered trees with edge weights summing to n, where edge weights are all greater than zero, and the sequences of edge weights in all downward paths are strictly increasing.

1, 1, 2, 5, 11, 26, 61, 142, 334, 785, 1845, 4339, 10211, 24030, 56560, 133143, 313433, 737906, 1737275, 4090206, 9630067, 22673482, 53383917, 125691264, 295938451, 696785116, 1640579144, 3862745470, 9094847357, 21413863699, 50419073794, 118712060012, 279508439419

Offset

0,3

Links

Table of n, a(n) for n=0..32.

Formula

G.f.: G_0(x) where G_k(x) = 1/(1 - Sum_{i>k} x^i * G_i(x)).

Example

The following tree with sum of edge weights 15 contains downward paths of edge weights (1), (2,3,4), and (2,3,5) all of which are weakly increasing. So this tree is counted under a(13) = 133143.
           o
        2 / \ 1
         o   o
      3 /
       o
    4 / \ 5
     o   o

Prog

(PARI)
w(j, k, N) = {if(k>N, 1, 1/(1 - sum(i=j+1, N, x^i * w(i, k+1, N-i+1))))}
Bx(N) = {my(x='x+O('x^(N+1))); Vec(w(0, 1, N)+ O('x^(N+1)))}
Bx(10)

Crossrefs

Cf. A000108, A000169, A000957, A001764, A036765, A384747, A384748.

Sequence in context: A238437 A191692 A182015 * A124217 A095981 A247471

Adjacent sequences: A384935 A384936 A384937 * A384939 A384940 A384941

Keyword

nonn

Author

John Tyler Rascoe, Jun 13 2025

Status

approved