A299038 Number A(n,k) of rooted trees with n nodes where each node has at most k children; square array A(n,k), n>=0, k>=0, read by antidiagonals.
1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 2, 1, 0, 1, 1, 1, 2, 3, 1, 0, 1, 1, 1, 2, 4, 6, 1, 0, 1, 1, 1, 2, 4, 8, 11, 1, 0, 1, 1, 1, 2, 4, 9, 17, 23, 1, 0, 1, 1, 1, 2, 4, 9, 19, 39, 46, 1, 0, 1, 1, 1, 2, 4, 9, 20, 45, 89, 98, 1, 0, 1, 1, 1, 2, 4, 9, 20, 47, 106, 211, 207, 1, 0
Offset: 0
Examples
Square array A(n,k) begins: 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... 0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... 0, 1, 3, 4, 4, 4, 4, 4, 4, 4, 4, ... 0, 1, 6, 8, 9, 9, 9, 9, 9, 9, 9, ... 0, 1, 11, 17, 19, 20, 20, 20, 20, 20, 20, ... 0, 1, 23, 39, 45, 47, 48, 48, 48, 48, 48, ... 0, 1, 46, 89, 106, 112, 114, 115, 115, 115, 115, ... 0, 1, 98, 211, 260, 277, 283, 285, 286, 286, 286, ... 0, 1, 207, 507, 643, 693, 710, 716, 718, 719, 719, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..140, flattened
Crossrefs
Programs
-
Maple
b:= proc(n, i, t, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)* b(n-i*j, i-1, t-j, k), j=0..min(t, n/i)))) end: A:= (n, k)-> `if`(n=0, 1, b(n-1$2, k$2)): seq(seq(A(n, d-n), n=0..d), d=0..14); -
Mathematica
b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i<1, 0, Sum[Binomial[ b[i-1, i-1, k, k]+j-1, j]*b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]]]; A[n_, k_] := If[n == 0, 1, b[n - 1, n - 1, k, k]]; Table[A[n, d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jun 04 2018, from Maple *) -
Python
from sympy import binomial from sympy.core.cache import cacheit @cacheit def b(n, i, t, k): return 1 if n==0 else 0 if i<1 else sum([binomial(b(i-1, i-1, k, k)+j-1, j)*b(n-i*j, i-1, t-j, k) for j in range(min(t, n//i)+1)]) def A(n, k): return 1 if n==0 else b(n-1, n-1, k, k) for d in range(15): print([A(n, d-n) for n in range(d+1)]) # Indranil Ghosh, Mar 02 2018, after Maple code
Formula
A(n,k) = Sum_{i=0..k} A244372(n,i) for n>0, A(0,k) = 1.