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,13

Links

Alois P. Heinz, Antidiagonals n = 1..141, flattened

Index entries for sequences related to rooted trees

Formula

A(n,k) = Sum_{j=1..k} A292086(n,j).

Example

:               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, ...

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<v, 0,
      `if`(v=n, 1, add(binomial(A(i, k)+j-1, j)*
       b(n-i*j, i-1, v-j, k), j=0..min(n/i, v)))))
    end:
A:= proc(n, k) option remember; `if`(n<2, n,
      add(b(n, n+1-j, j, k), j=2..min(n, k)))
    end:
seq(seq(A(n, 1+d-n), n=1..d), d=1..14);

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 *)

Crossrefs

Columns k=1-10 give: A063524, A001190, A268172, A292210, A292211, A292212, A292213, A292214, A292215, A292216.

Main diagonal gives A000669.

Cf. A244372, A288942, A292086.

Sequence in context: A283308 A339959 A255636 * A262163 A293112 A306910

Adjacent sequences: A292082 A292083 A292084 * A292086 A292087 A292088

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 08 2017

Status

approved