A318758 -id:A318758 - 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.

A255705 Number of 2n+1-node rooted trees in which the maximal number of nodes in paths starting at a leaf and ending at the first branching node or at the root equals n+1.

Original entry on oeis.org

1, 1, 3, 8, 22, 60, 167, 465, 1306, 3681, 10422, 29597, 84313, 240757, 689035, 1975753, 5675145, 16326198, 47032200, 135658367, 391733593, 1132357784, 3276330780, 9487885056, 27497891241, 79753806451, 231474005120, 672250119756, 1953523496677, 5680002466125

Offset: 0

Alois P. Heinz, Mar 02 2015

nonn

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

Cf. A255636, A255704, A318754, A318758.

with(numtheory):
g:= proc(n, k) option remember; `if`(n=0, 1, add(add(d*(g(d-1, k)-
      `if`(d=k, 1, 0)), d=divisors(j))*g(n-j, k), j=1..n)/n)
    end:
a:= a-> g(2*n, n+1) -`if`(n=0, 0, g(2*n, n)):
seq(a(n), n=0..40);

g[n_, k_] := g[n, k] = If[n == 0, 1, Sum[DivisorSum[j, #*(g[# - 1, k] - If[# == k, 1, 0]) &]*g[n - j, k], {j, 1, n}]/n];
a[n_] :=  g[2n, n+1] - If[n == 0, 0, g[2n, n]];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 24 2017, translated from Maple *)

a(n) = A255704(2*n+1,n+1).
a(n) ~ c * d^n / sqrt(n), where d = A051491 = 2.955765285651994974714817524... and c = 0.70755335886284109851526791506579... . - Vaclav Kotesovec, Feb 28 2016
a(n) = A318754(2n+2,n+1) = A318758(2n+2,n+1). - Alois P. Heinz, Sep 02 2018

A318859 Number of rooted trees with n nodes such that two equals the maximal number of isomorphic subtrees extending from the same node.

Original entry on oeis.org

0, 1, 1, 4, 9, 22, 54, 138, 346, 889, 2285, 5928, 15436, 40424, 106230, 280305, 741912, 1969816, 5243942, 13995807, 37439883, 100371907, 269623436, 725638613, 1956352468, 5283171593, 14289645110, 38707131195, 104995130162, 285184002486, 775586517781

Offset: 2

Alois P. Heinz, Sep 04 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 2..2213

Column k=2 of 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)):
a:= n-> (k-> A(n, k)-A(n, k-1))(2):
seq(a(n), n=2..32);

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]];
a[n_] := A[n, 2] - A[n, 1];
Table[a[n], {n, 2, 32}] (* Jean-François Alcover, Dec 01 2023, after Alois P. Heinz *)

A318860 Number of rooted trees with n nodes such that three equals the maximal number of isomorphic subtrees extending from the same node.

Original entry on oeis.org

0, 1, 1, 3, 9, 23, 60, 164, 443, 1209, 3319, 9150, 25326, 70335, 195870, 546823, 1529935, 4288662, 12042447, 33866604, 95373852, 268925258, 759157224, 2145298117, 6068251826, 17180172176, 48680092670, 138041661905, 391725281701, 1112360700816, 3160707529077

Offset: 3

Alois P. Heinz, Sep 04 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 3..2158

Column k=3 of 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)):
a:= n-> (k-> A(n, k)-A(n, k-1))(3):
seq(a(n), n=3..33);

A318861 Number of rooted trees with n nodes such that four equals the maximal number of isomorphic subtrees extending from the same node.

Original entry on oeis.org

0, 1, 1, 3, 8, 23, 61, 167, 461, 1285, 3587, 10069, 28350, 80101, 226861, 644064, 1832113, 5221138, 14902620, 42597586, 121917123, 349343846, 1002080752, 2877234480, 8268665140, 23782254063, 68454314588, 197176382059, 568320901793, 1639070974728, 4729877188814

Offset: 4

Alois P. Heinz, Sep 04 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 4..2143

Column k=4 of 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)):
a:= n-> (k-> A(n, k)-A(n, k-1))(4):
seq(a(n), n=4..34);

A318862 Number of rooted trees with n nodes such that five equals the maximal number of isomorphic subtrees extending from the same node.

Original entry on oeis.org

0, 1, 1, 3, 8, 22, 61, 168, 465, 1302, 3659, 10329, 29247, 83076, 236567, 675191, 1930857, 5531409, 15870783, 45600643, 131187583, 377844713, 1089401822, 3143970659, 9081351051, 26252708661, 75949137535, 219873546468, 636947053248, 1846268556446, 5354642063044

Offset: 5

Alois P. Heinz, Sep 04 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 5..2138

Column k=5 of 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)):
a:= n-> (k-> A(n, k)-A(n, k-1))(5):
seq(a(n), n=5..35);

A318863 Number of rooted trees with n nodes such that six equals the maximal number of isomorphic subtrees extending from the same node.

Original entry on oeis.org

0, 1, 1, 3, 8, 22, 60, 168, 466, 1306, 3677, 10400, 29503, 83964, 239523, 684855, 1961933, 5630300, 16182535, 46576693, 134225427, 387254945, 1118433179, 3233228736, 9354963666, 27089288339, 78501221909, 227643444368, 660560681614, 1917918979943, 5571738217340

Offset: 6

Alois P. Heinz, Sep 04 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 6..2137

Column k=6 of 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)):
a:= n-> (k-> A(n, k)-A(n, k-1))(6):
seq(a(n), n=6..36);

A318864 Number of rooted trees with n nodes such that seven equals the maximal number of isomorphic subtrees extending from the same node.

Original entry on oeis.org

0, 1, 1, 3, 8, 22, 60, 167, 466, 1307, 3681, 10418, 29575, 84219, 240407, 687802, 1971576, 5661335, 16281377, 46888590, 135202932, 390300559, 1127877757, 3262398334, 9444747407, 27364824226, 79344643855, 230219356666, 668412171376, 1941808202980, 5644309042885

Offset: 7

Alois P. Heinz, Sep 04 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 7..2137

Column k=7 of 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)):
a:= n-> (k-> A(n, k)-A(n, k-1))(7):
seq(a(n), n=7..37);

A318865 Number of rooted trees with n nodes such that eight equals the maximal number of isomorphic subtrees extending from the same node.

Original entry on oeis.org

0, 1, 1, 3, 8, 22, 60, 167, 465, 1307, 3682, 10422, 29593, 84291, 240663, 688685, 1974519, 5670969, 16312391, 46987389, 135514781, 391278211, 1130924824, 3271850658, 9473951229, 27454745755, 79620703854, 231064697016, 670994912068, 1949683485967, 5668279789793

Offset: 8

Alois P. Heinz, Sep 04 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 8..2137

Column k=8 of 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)):
a:= n-> (k-> A(n, k)-A(n, k-1))(8):
seq(a(n), n=8..38);

A318866 Number of rooted trees with n nodes such that nine equals the maximal number of isomorphic subtrees extending from the same node.

Original entry on oeis.org

0, 1, 1, 3, 8, 22, 60, 167, 465, 1306, 3682, 10423, 29597, 84309, 240735, 688941, 1975403, 5673911, 16322021, 47018394, 135613559, 391590017, 1131902426, 3274897873, 9483405008, 27483957321, 79710659583, 231340894684, 671840776074, 1952268143504, 5676161896298

Offset: 9

Alois P. Heinz, Sep 04 2018

nonn

Alois P. Heinz, Table of n, a(n) for n = 9..2138

Column k=9 of 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)):
a:= n-> (k-> A(n, k)-A(n, k-1))(9):
seq(a(n), n=9..39);

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

A255705 Number of 2n+1-node rooted trees in which the maximal number of nodes in paths starting at a leaf and ending at the first branching node or at the root equals n+1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A318859 Number of rooted trees with n nodes such that two equals the maximal number of isomorphic subtrees extending from the same node.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A318860 Number of rooted trees with n nodes such that three equals the maximal number of isomorphic subtrees extending from the same node.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A318861 Number of rooted trees with n nodes such that four equals the maximal number of isomorphic subtrees extending from the same node.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A318862 Number of rooted trees with n nodes such that five equals the maximal number of isomorphic subtrees extending from the same node.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A318863 Number of rooted trees with n nodes such that six equals the maximal number of isomorphic subtrees extending from the same node.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A318864 Number of rooted trees with n nodes such that seven equals the maximal number of isomorphic subtrees extending from the same node.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A318865 Number of rooted trees with n nodes such that eight equals the maximal number of isomorphic subtrees extending from the same node.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

A318866 Number of rooted trees with n nodes such that nine equals the maximal number of isomorphic subtrees extending from the same node.