A384685 Triangle read by rows: T(n,k) is the number of rooted ordered trees with node weights summing to n, where the root has weight 0, all internal nodes have weight 1, and leaf nodes have weights in {1,...,k}.

1, 0, 1, 0, 2, 3, 0, 5, 8, 9, 0, 14, 25, 28, 29, 0, 42, 83, 95, 98, 99, 0, 132, 289, 337, 349, 352, 353, 0, 429, 1041, 1236, 1285, 1297, 1300, 1301, 0, 1430, 3847, 4652, 4854, 4903, 4915, 4918, 4919, 0, 4862, 14504, 17865, 18709, 18912, 18961, 18973, 18976, 18977

Offset: 0

Author

John Tyler Rascoe, Jun 06 2025

Keywords

• nonn
• easy
• tabl

Examples

			Triangle begins:
    k=0     1     2     3     4     5     6     7      8
 n=0 [1]
 n=1 [0,    1]
 n=2 [0,    2,    3]
 n=3 [0,    5,    8,    9]
 n=4 [0,   14,   25,   28,   29]
 n=5 [0,   42,   83,   95,   98,   99]
 n=6 [0,  132,  289,  337,  349,  352,  353]
 n=7 [0,  429, 1041, 1236, 1285, 1297, 1300, 1301]
 n=8 [0, 1430, 3847, 4652, 4854, 4903, 4915, 4918, 4919]
...
T(2,2) = 3 counts:
  o    o      o
  |    |     / \
 (2)  (1)  (1) (1)
       |
      (1)
		

Crossrefs

Cf. (column k=1) A000108, A078481, A078482, A088218, (column k=2) A143330, A380761, A384613.

Programs

PARI

b(k) = {(x^2-x^(k+1))/(1-x)}
P(N,k) = {my(x='x+O('x^N)); Vec((1-b(k)-sqrt((b(k)-1)^2-4*x))/(2*x))}
T(max_row) = { my( N = max_row+1, v = vector(N, i, if(i==1,1,0))~); for(k=1,N, v=matconcat([v,P(N+1,k)~])); vector(N,n, vector(n,k,v[n,k]))}

Formula

G.f. of column k is (1 - b(k,x) - sqrt((b(k,x) - 1)^2 - 4*x))/(2*x) where b(k,x) = (x^2 - x^(k + 1))/(1 - x).

T(n,k) = T(n,n) for k > n.