A318753 Number A(n,k) of rooted trees with n nodes such that no more than k subtrees extending from the same node have the same number of nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 2, 3, 3, 0, 0, 1, 1, 2, 4, 7, 6, 0, 0, 1, 1, 2, 4, 8, 15, 12, 0, 0, 1, 1, 2, 4, 9, 18, 34, 25, 0, 0, 1, 1, 2, 4, 9, 19, 43, 79, 51, 0, 0, 1, 1, 2, 4, 9, 20, 46, 102, 190, 111, 0, 0, 1, 1, 2, 4, 9, 20, 47, 110, 250, 457, 240, 0

Offset

0,19

Links

Alois P. Heinz, Antidiagonals n = 0..200, flattened

Formula

A(n,k) = Sum_{j=0..k} A318754(n,j) for n > 0.

A(n,n+j) = A000081(n) for j >= -1.

Example

Square array A(n,k) begins:
  0,  0,  0,   0,   0,   0,   0,   0,   0, ...
  1,  1,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,  2,   2,   2,   2,   2,   2,   2, ...
  0,  2,  3,   4,   4,   4,   4,   4,   4, ...
  0,  3,  7,   8,   9,   9,   9,   9,   9, ...
  0,  6, 15,  18,  19,  20,  20,  20,  20, ...
  0, 12, 34,  43,  46,  47,  48,  48,  48, ...
  0, 25, 79, 102, 110, 113, 114, 115, 115, ...

Maple

g:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(A(i, k)+j-1, j)*g(n-i*j, i-1, k), j=0..min(k, n/i))))
    end:
A:= (n, k)-> g(n-1$2, k):
seq(seq(A(n, d-n), n=0..d), d=0..14);

Mathematica

g[n_, i_, k_] := g[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[A[i, k] + j - 1, j]*g[n - i*j, i - 1, k], {j, 0, Min[k, n/i]}]]];
A[n_, k_] := g[n - 1, n - 1, k];
Table[A[n, d - n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, May 27 2019, after Alois P. Heinz *)

Crossrefs

Columns k=0-10 give: A063524, A032305, A213920, A318797, A318798, A318799, A318800, A318801, A318802, A318803, A318804.

Rows n=0-2 give: A000004, A000012, A057427.

Main diagonal gives A000081.

Cf. A318754.

Sequence in context: A131555 A373607 A293209 * A318757 A263834 A263754

Adjacent sequences: A318750 A318751 A318752 * A318754 A318755 A318756

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 02 2018

Status

approved