A292085 Number A(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes or outdegrees larger than k; square array A(n,k), n>=0, k>=0, read by antidiagonals.
1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 2, 0, 1, 1, 2, 4, 3, 0, 1, 1, 2, 5, 9, 6, 0, 1, 1, 2, 5, 11, 23, 11, 0, 1, 1, 2, 5, 12, 30, 58, 23, 0, 1, 1, 2, 5, 12, 32, 80, 156, 46, 0, 1, 1, 2, 5, 12, 33, 87, 228, 426, 98, 0, 1, 1, 2, 5, 12, 33, 89, 251, 656, 1194, 207, 0
Offset: 1
Examples
: T(4,3) = 4 : : : : o o o o : : / \ / \ / \ /|\ : : o N o o o N o N N : : / \ ( ) ( ) /|\ ( ) : : o N N N N N N N N N N : : ( ) : : N N : : : Square array A(n,k) begins: 1, 1, 1, 1, 1, 1, 1, 1, ... 0, 1, 1, 1, 1, 1, 1, 1, ... 0, 1, 2, 2, 2, 2, 2, 2, ... 0, 2, 4, 5, 5, 5, 5, 5, ... 0, 3, 9, 11, 12, 12, 12, 12, ... 0, 6, 23, 30, 32, 33, 33, 33, ... 0, 11, 58, 80, 87, 89, 90, 90, ... 0, 23, 156, 228, 251, 258, 260, 261, ...
Links
Crossrefs
Programs
-
Maple
b:= proc(n, i, v, k) option remember; `if`(n=0, `if`(v=0, 1, 0), `if`(i<1 or v<1 or n -
Mathematica
b[n_, i_, v_, k_] := b[n, i, v, k] = If[n == 0, If[v == 0, 1, 0], If[i < 1 || v < 1 || n < v, 0, If[v == n, 1, Sum[Binomial[A[i, k] + j - 1, j]*b[n - i*j, i - 1, v - j, k], {j, 0, Min[n/i, v]}]]]]; A[n_, k_] := A[n, k] = If[n < 2, n, Sum[b[n, n + 1 - j, j, k], {j, 2, Min[n, k]}]]; Table[Table[A[n, 1 + d - n], {n, 1, d}], {d, 1, 14}] // Flatten (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)
Formula
A(n,k) = Sum_{j=1..k} A292086(n,j).