A318754 -id:A318754 - cp's OEIS frontend

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

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, A032305, A213920, A318797, A318798, A318799, A318800, A318801, A318802, A318803, A318804.
Rows n=0-2 give: A000004, A000012, A057427.
Main diagonal gives A000081.
Cf. A318754.

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

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

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

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

A318758 Number T(n,k) of rooted trees with n nodes such that k equals the maximal number of isomorphic subtrees extending from the same node; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 1, 1, 0, 3, 4, 1, 1, 0, 6, 9, 3, 1, 1, 0, 12, 22, 9, 3, 1, 1, 0, 25, 54, 23, 8, 3, 1, 1, 0, 52, 138, 60, 23, 8, 3, 1, 1, 0, 113, 346, 164, 61, 22, 8, 3, 1, 1, 0, 247, 889, 443, 167, 61, 22, 8, 3, 1, 1, 0, 548, 2285, 1209, 461, 168, 60, 22, 8, 3, 1, 1

Offset: 1

Alois P. Heinz, Sep 02 2018

T(n,k) is defined for n,k >= 0. The triangle contains only the terms with k < n. T(n,k) = 0 for k >= n.

			Triangle T(n,k) begins:
  1;
  0,   1;
  0,   1,   1;
  0,   2,   1,   1;
  0,   3,   4,   1,  1;
  0,   6,   9,   3,  1,  1;
  0,  12,  22,   9,  3,  1, 1;
  0,  25,  54,  23,  8,  3, 1, 1;
  0,  52, 138,  60, 23,  8, 3, 1, 1;
  0, 113, 346, 164, 61, 22, 8, 3, 1, 1;

Alois P. Heinz, Rows n = 1..200, flattened

Columns k=0-10 give: A063524, A004111 (for n>1), A318859, A318860, A318861, A318862, A318863, A318864, A318865, A318866, A318867.
Row sums give A000081.
T(2n+2,n+1) gives A255705.
Cf. A318754, A318757.

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)):
T:= (n, k)-> A(n, k)-`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..n-1), n=1..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]];
T[n_, k_] := A[n, k] - If[k == 0, 0, A[n, k - 1]];
Table[T[n, k], {n, 1, 14}, {k, 0, n - 1}] // Flatten (* Jean-François Alcover, May 11 2019, after Alois P. Heinz *)

T(n,k) = A318757(n,k) - A318757(n,k-1) for k > 0, A(n,0) = A063524(n).

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

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

Original entry on oeis.org

0, 1, 1, 4, 9, 22, 54, 139, 346, 892, 2290, 5945, 15465, 40527, 106308, 280629, 742107, 1969394, 5239322, 13980900, 37368692, 100157418, 268900827, 723400570, 1949440608, 5262932344, 14227803491, 38529294292, 104473993774, 283672750693, 771229441388

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

g:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g(i-1$2, 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) -g(n-1$2, k-1))(2):
seq(a(n), n=2..32);

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

Original entry on oeis.org

0, 1, 1, 3, 9, 23, 60, 166, 447, 1219, 3344, 9214, 25493, 70853, 197150, 550259, 1539767, 4314746, 12112304, 34063256, 95904943, 270375031, 763193304, 2156328194, 6098563949, 17264760959, 48912296290, 138683094562, 393514686620, 1117304554815, 3174397805762

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

g:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g(i-1$2, 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) -g(n-1$2, k-1))(3):
seq(a(n), n=3..33);

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

Original entry on oeis.org

0, 1, 1, 3, 8, 23, 61, 167, 461, 1288, 3593, 10084, 28381, 80218, 227156, 644864, 1834290, 5227297, 14919502, 42644478, 122047963, 349716506, 1003120145, 2880163515, 8276937322, 23805829084, 68521035251, 197365718477, 568859465838, 1640609651599, 4734261078026

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

g:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g(i-1$2, 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) -g(n-1$2, k-1))(4):
seq(a(n), n=4..34);

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

Original entry on oeis.org

0, 1, 1, 3, 8, 22, 61, 168, 465, 1302, 3659, 10333, 29255, 83096, 236609, 675311, 1931235, 5532421, 15873557, 45608348, 131208906, 377906025, 1089573851, 3144456980, 9082730826, 26256633715, 75960348880, 219905556560, 637038643771, 1846531053341, 5355395451034

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

g:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g(i-1$2, 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) -g(n-1$2, k-1))(5):
seq(a(n), n=5..35);

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

Original entry on oeis.org

0, 1, 1, 3, 8, 22, 60, 168, 466, 1306, 3677, 10400, 29503, 83969, 239533, 684880, 1961986, 5630451, 16182950, 46577929, 134228796, 387264335, 1118459507, 3233302665, 9355173164, 27089886520, 78502923212, 227648300409, 660574571072, 1917958785876, 5571852459248

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

g:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g(i-1$2, 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) -g(n-1$2, k-1))(6):
seq(a(n), n=6..36);

A318822 Number of rooted trees with n nodes such that seven equals the maximal number of subtrees of the same size 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, 687808, 1971588, 5661365, 16281441, 46888772, 135203432, 390301957, 1127881755, 3262409450, 9444778623, 27364912377, 79344893246, 230220066260, 668414195077, 1941813994013, 5644325624891

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

g:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g(i-1$2, 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) -g(n-1$2, k-1))(7):
seq(a(n), n=7..37);

A318823 Number of rooted trees with n nodes such that eight equals the maximal number of subtrees of the same size 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, 5670976, 16312405, 46987424, 135514856, 391278424, 1130925409, 3271852293, 9473955776, 27454758665, 79620740071, 231064799358, 670995202298, 1949684311164, 5668282144436

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

g:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g(i-1$2, 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) -g(n-1$2, k-1))(8):
seq(a(n), n=8..38);

cp's OEIS Frontend

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A318758 Number T(n,k) of rooted trees with n nodes such that k equals the maximal number of isomorphic subtrees extending from the same node; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

Views

Author

Keywords

Comments

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

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

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

Views

Author

Keywords

Links

Crossrefs