A245102 -id:A245102 - cp's OEIS frontend

A034781 Triangle of number of rooted trees with n >= 2 nodes and height h >= 1.

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 6, 8, 4, 1, 1, 10, 18, 13, 5, 1, 1, 14, 38, 36, 19, 6, 1, 1, 21, 76, 93, 61, 26, 7, 1, 1, 29, 147, 225, 180, 94, 34, 8, 1, 1, 41, 277, 528, 498, 308, 136, 43, 9, 1, 1, 55, 509, 1198, 1323, 941, 487, 188, 53, 10, 1

Offset: 2

N. J. A. Sloane

			Triangle begins:
  1;
  1  1;
  1  2  1;
  1  4  3  1;
  1  6  8  4  1;
  1 10 18 13  5  1;
  1 14 38 36 19  6 1;
thus there are 10 trees with 7 nodes and height 2.

Alois P. Heinz, Rows n = 2..142, flattened
Marko Riedel, Counting the number of rooted trees of a certain height
Marko Riedel, Maple code for sequence (OGF)
J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
J. Riordan, The enumeration of trees by height and diameter, IBM Journal 4 (1960), 473-478. (Annotated scanned copy)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Columns h=2-10 give: A000065, A000235, A000299, A000342, A000393, A000418, A000429, A126085, A245068.
T(2n,n) = A245102(n), T(2n+1,n) = A245103(n).
Row sums give A000081.
Cf. A001853, A227819, A375467.

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1 or k<1, 0,
     add(binomial(b((i-1)$2, k-1)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
    end:
T:= (n, k)-> b((n-1)$2, k) -b((n-1)$2, k-1):
seq(seq(T(n, k), k=1..n-1), n=2..16);  # Alois P. Heinz, Jul 31 2013

Drop[Map[Select[#, # > 0 &] &,
   Transpose[
    Prepend[Table[
      f[n_] :=
       Nest[CoefficientList[
          Series[Product[1/(1 - x^i)^#[[i]], {i, 1, Length[#]}], {x,
            0, 10}], x] &, {1}, n]; f[m] - f[m - 1], {m, 2, 10}],
Prepend[Table[1, {10}], 0]]]], 1] // Grid (* Geoffrey Critzer, Aug 01 2013 *)
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i<1 || k<1, 0, Sum[Binomial[b[i-1, i-1, k-1]+j-1, j]*b[n-i*j, i-1, k], {j, 0, n/i}]]]; T[n_, k_] := b[n-1, n-1, k]-b[n-1, n-1, k-1]; Table[T[n, k], {n, 2, 16}, {k, 1, n-1}] // Flatten (* Jean-François Alcover, Feb 11 2014, after Alois P. Heinz *)

def A034781(n, k): return A375467(n, k) - A375467(n, k - 1)
for n in range(2, 10): print([A034781(n, k) for k in range(2, n + 1)])
# Peter Luschny, Aug 30 2024

Reference gives recurrence.

T(n, k) = A375467(n, k) - A375467(n, k - 1). - Peter Luschny, Aug 30 2024

More terms from Victoria A Sapko (vsapko(AT)canes.gsw.edu), Sep 19 2003

A245103 Number of (2n+1)-node rooted trees of height n.

Original entry on oeis.org

1, 1, 4, 18, 93, 498, 2744, 15349, 86802, 494769, 2837412, 16351036, 94599339, 549118128, 3196397701, 18651028188, 109057492901, 638863803720, 3748605725140, 22027421351633, 129606128716906, 763484925360476, 4502370205339221, 26577052185126059

Offset: 0

Alois P. Heinz, Jul 11 2014

nonn

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

Cf. A034781.

a(n) = A034781(2n+1,n).

a(n) ~ c * d^n / sqrt(n), where d = 6.0313827950978605329935... (same as for A245102 and A339440), c = 0.14566140512597547487... . - Vaclav Kotesovec, Jul 12 2014

A339440 Number of linear forests with n rooted trees and 2*n-1 nodes.

Original entry on oeis.org

0, 1, 2, 9, 44, 230, 1236, 6790, 37832, 213057, 1209660, 6912367, 39705516, 229055918, 1326168018, 7701734250, 44846271632, 261735599172, 1530650010312, 8967361033572, 52619233554120, 309203221308702, 1819290987055630, 10716835948503349, 63196331969007264

Offset: 0

Alois P. Heinz, Dec 04 2020

nonn

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

Cf. A339067, A245102, A245103.

b:= proc(n) option remember; `if`(n<2, n, (add(add(d*b(d),
      d=numtheory[divisors](j))*b(n-j), j=1..n-1))/(n-1))
    end:
T:= proc(n, k) option remember; `if`(k=1, b(n), (t->
      add(T(j, t)*T(n-j, k-t), j=1..n-1))(iquo(k, 2)))
    end:
a:= n-> T(2*n-1, n):
seq(a(n), n=0..24);

b[n_] := b[n] = If[n<2, n, (Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n - j], {j, 1, n - 1}])/(n - 1)];
T[n_, k_] := T[n, k] = If[k == 1, b[n], With[{t = Quotient[k, 2]}, Sum[T[j, t]*T[n - j, k - t], {j, 1, n - 1}]]];
a[n_] := T[2n-1, n];
a /@ Range[0, 24] (* Jean-François Alcover, Jan 03 2021, after Alois P. Heinz *)

a(n) = A339067(2n-1,n).

a(n) ~ c * d^n / sqrt(n), where d = 6.031382795097860532993547039674008662345079835351392549515262162478014679... and c = 0.05599525103242350197279211300654208236718263537075... - Vaclav Kotesovec, Dec 18 2020

cp's OEIS Frontend

A034781 Triangle of number of rooted trees with n >= 2 nodes and height h >= 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A245103 Number of (2n+1)-node rooted trees of height n.

Views

Author

Keywords

Links

Crossrefs

Formula

A339440 Number of linear forests with n rooted trees and 2*n-1 nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula