A292086 Number T(n,k) of (unlabeled) rooted trees with n leaf nodes and without unary nodes such that k is the maximum of 1 and the node outdegrees; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 3, 6, 2, 1, 0, 6, 17, 7, 2, 1, 0, 11, 47, 22, 7, 2, 1, 0, 23, 133, 72, 23, 7, 2, 1, 0, 46, 380, 230, 77, 23, 7, 2, 1, 0, 98, 1096, 751, 256, 78, 23, 7, 2, 1, 0, 207, 3186, 2442, 861, 261, 78, 23, 7, 2, 1, 0, 451, 9351, 8006, 2897, 887, 262, 78, 23, 7, 2, 1

Offset: 1

Author

Alois P. Heinz, Sep 08 2017

Keywords

• nonn
• tabl

Examples

			:   T(4,2) = 2        :   T(4,3) = 2      : T(4,4) = 1 :
:                     :                   :            :
:       o       o     :      o       o    :     o      :
:      / \     / \    :     / \     /|\   :   /( )\    :
:     o   N   o   o   :    o   N   o N N  :  N N N N   :
:    / \     ( ) ( )  :   /|\     ( )     :            :
:   o   N    N N N N  :  N N N    N N     :            :
:  ( )                :                   :            :
:  N N                :                   :            :
:                     :                   :            :
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1,   1;
  0,  2,   2,   1;
  0,  3,   6,   2,  1;
  0,  6,  17,   7,  2,  1;
  0, 11,  47,  22,  7,  2, 1;
  0, 23, 133,  72, 23,  7, 2, 1;
  0, 46, 380, 230, 77, 23, 7, 2, 1;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• Index entries for sequences related to rooted trees

Crossrefs

Columns k=1-10 give: A063524, A001190 (for n>1), A292229, A292230, A292231, A292232, A292233, A292234, A292235, A292236.

Row sums give A000669.

Limit of reversed rows gives A292087.

Cf. A244372, A288942, A292085.

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 A(n, k)-`if`(k=1, 0, A(n, k-1)):
seq(seq(T(n, k), k=1..n), n=1..15);

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]}]];
T[n_, k_] := A[n, k] - If[k == 1, 0, A[n, k - 1]];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 15}] // Flatten (* Jean-François Alcover, Nov 07 2017, after Alois P. Heinz *)

Formula

T(n,k) = A292085(n,k) - A292085(n,k-1) for k>2, T(n,1) = A292085(n,1).