A318857 -id:A318857 - cp's OEIS frontend

A318757 Number A(n,k) of rooted trees with n nodes such that no more than k isomorphic subtrees extend from the same node; 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, 52, 0, 0, 1, 1, 2, 4, 9, 20, 46, 102, 190, 113, 0, 0, 1, 1, 2, 4, 9, 20, 47, 110, 250, 459, 247, 0

Offset: 0

Alois P. Heinz, Sep 02 2018

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

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

Columns k=0-10 give: A063524, A004111, A248869, A318850, A318851, A318852, A318853, A318854, A318855, A318856, A318857.
Main diagonal gives A000081.
Cf. A318753, A318758.

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

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

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

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

A318804 Number of rooted trees with n nodes such that no more than ten subtrees of the same size extend from the same node.

Original entry on oeis.org

0, 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4765, 12484, 32968, 87798, 235346, 634752, 1720897, 4687949, 12824195, 35216118, 97039045, 268237121, 743594937, 2066803841, 5758576675, 16080698759, 44998355630, 126161517745, 354354779794, 996963790045, 2809334906744, 7928088014833, 22404525682610

Offset: 0

Alois P. Heinz, Sep 03 2018

nonn

This differs from A318857 first at n=34.

Alois P. Heinz, Table of n, a(n) for n = 0..2136

Column k=10 of A318753.

Cf. A318857.

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

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula