A000235 -id:A000235 - 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

A001383 Number of n-node rooted trees of height at most 3.

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 15, 29, 53, 98, 177, 319, 565, 1001, 1749, 3047, 5264, 9054, 15467, 26320, 44532, 75054, 125904, 210413, 350215, 580901, 960035, 1581534, 2596913, 4251486, 6939635, 11296231, 18337815, 29692431, 47956995, 77271074, 124212966

Offset: 0

N. J. A. Sloane

a(n+1) is also the number of n-vertex graphs that do not contain a P_4, C_4, or K_4 as induced subgraph (K_4-free trivially perfect graphs, cf. A123467). - Falk Hüffner, Jan 10 2016

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n=0..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 62
J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000041, A001383-A001385, A034823-A034826.

s[ 2 ] := x/product('1-x^i','i'=1..30); # G.f. for trees of ht <=2, A000041
for k from 3 to 12 do # gets g.f. for trees of ht <= 3,4,5,...
s[ k ] := series(x/product('(1-x^i)^coeff(s[ k-1 ],x,i)','i'=1..30),x,31); od:
# For Maple program see link in A000235.
with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d,j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: A000041:= etr(n-> 1): a:= n->`if`(n=0,1, etr(k-> A000041(k-1))(n-1)): seq(a(n), n=0..40);  # Alois P. Heinz, Sep 08 2008

m = 36; CoefficientList[ Series[x*Product[(1 - x^k)^(-PartitionsP[k - 1]), {k, 1, m}], {x, 0, m}], x] // Rest // Prepend[#, 1] & (* Jean-François Alcover, Jul 05 2011, after g.f. *)

{a(n)=polcoeff(1+x*exp(sum(m=1,n,x^m/m/prod(k=1,n\m+1,1-x^(m*k)+x*O(x^n)))),n)} \\ Paul D. Hanna, Nov 01 2012

G.f.: S[ 3 ] := x*Product (1 - x^k)^(-p(k-1)), where p(k) = number of partitions of k.
a(n+1) is the Euler transform of p(n-1), where p() = A000041 is the partition function. - Franklin T. Adams-Watters, Mar 01 2006
G.f.: 1 + x*exp( Sum_{n>=1} x^n/n * Product_{k>=1} 1/(1 - x^(n*k)) ). - Paul D. Hanna, Nov 01 2012

A001385 Number of n-node trees of height at most 5.

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 20, 47, 108, 252, 582, 1345, 3086, 7072, 16121, 36667, 83099, 187885, 423610, 953033, 2139158, 4792126, 10714105, 23911794, 53273599, 118497834, 263164833, 583582570, 1292276355, 2857691087, 6311058671, 13919982308, 30664998056, 67473574130

Offset: 0

N. J. A. Sloane

nonn

a(n+1) is also the number of n-vertex graphs that do not contain a P_4, C_4, or K_6 as induced subgraph (K_6-free trivially perfect graphs, cf. A123467). - Falk Hüffner, Jan 10 2016

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n=0..200
J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

See A001383 for details.

For Maple program see link in A000235.
with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d,j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: shr:= proc(p) n->`if`(n=0, 1,p(n-1)) end: b[0]:= etr(n->1): for j from 1 to 3 do b[j]:= etr(shr(b[j-1])) od: a:= shr(b[3]): seq(a(n), n=0..35); # Alois P. Heinz, Sep 08 2008

Prepend[Nest[CoefficientList[Series[Product[1/(1-x^i)^#[[i]],{i,1,Length[#]}],{x,0,40}],x]&,{1},5],1] (* Geoffrey Critzer, Aug 01 2013 *)

Take Euler transform of A001384 and shift right. (Christian G. Bower)

A034823 Number of n-node rooted trees of height at most 6.

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 20, 48, 114, 278, 676, 1653, 4027, 9816, 23843, 57833, 139908, 337856, 814127, 1958524, 4703322, 11278027, 27003707, 64571463, 154207616, 367841733, 876450881, 2086098057, 4960230005, 11782852600, 27963874395, 66307010599

Offset: 0

N. J. A. Sloane

nonn

N. J. A. Sloane, Table of n, a(n) for n=0..200
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

See A001383 for details.

For Maple program see link in A000235.
with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d,j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: shr:= proc(p) n->`if`(n=0, 1,p(n-1)) end: b[0]:= etr(n->1): for j from 1 to 4 do b[j]:= etr(shr(b[j-1])) od: a:= shr(b[4]): seq(a(n), n=0..31); # Alois P. Heinz, Sep 08 2008

Prepend[Nest[CoefficientList[Series[Product[1/(1-x^i)^#[[i]],{i,1,Length[#]}],{x,0,40}],x]&,{1},6],1] (* Geoffrey Critzer, Aug 01 2013 *)

Take Euler transform of A001385 and shift right. (Christian G. Bower).

A001384 Number of n-node trees of height at most 4.

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 19, 42, 89, 191, 402, 847, 1763, 3667, 7564, 15564, 31851, 64987, 132031, 267471, 539949, 1087004, 2181796, 4367927, 8721533, 17372967, 34524291, 68456755, 135446896, 267444085, 527027186, 1036591718, 2035083599

Offset: 0

N. J. A. Sloane

nonn

a(n+1) is also the number of n-vertex graphs that do not contain a P_4, C_4, or K_5 as induced subgraph (K_5-free trivially perfect graphs, cf. A123467). - Falk Hüffner, Jan 10 2016

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n=0..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 63
J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

See A001383 for details.

For Maple program see link in A000235.
with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d,j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: A000041:= etr(n->1): b1:= etr(k-> A000041(k-1)): A001383:= n->`if`(n=0,1,b1(n-1)): b2:= etr(A001383): a:= n->`if`(n=0,1,b2(n-1)): seq(a(n), n=0..40); # Alois P. Heinz, Sep 08 2008

Prepend[Nest[CoefficientList[Series[Product[1/(1-x^i)^#[[i]],{i,1,Length[#]}],{x,0,40}],x]&,{1},4],1] (* Geoffrey Critzer, Aug 01 2013 *)

Take Euler transform of A001383 and shift right. (Christian G. Bower)

A034824 Number of n-node rooted trees of height at most 7.

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 20, 48, 115, 285, 710, 1789, 4514, 11431, 28922, 73182, 184917, 466755, 1176393, 2961205, 7443770, 18689435, 46869152, 117412440, 293832126, 734645046, 1835147741, 4580420719, 11423511895, 28469058647, 70899220083, 176449174539, 438854372942

Offset: 0

N. J. A. Sloane

nonn

N. J. A. Sloane, Table of n, a(n) for n=0..200
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

See A001383 for details.

For Maple program see link in A000235.
with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d,j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: shr:= proc(p) n->`if`(n=0, 1,p(n-1)) end: b[0]:= etr(n->1): for j from 1 to 5 do b[j]:= etr(shr(b[j-1])) od: a:= shr(b[5]): seq(a(n), n=0..35); # Alois P. Heinz, Sep 08 2008

Prepend[Nest[CoefficientList[Series[Product[1/(1-x^i)^#[[i]], {i, 1, Length[#]}], {x, 0, 40}], x]&, {1}, 7], 1] (* Geoffrey Critzer, Aug 01 2013 *)

Take Euler transform of A034823 and shift right. (Christian G. Bower).

A000550 Number of trees of diameter 7.

Original entry on oeis.org

1, 3, 14, 42, 128, 334, 850, 2010, 4625, 10201, 21990, 46108, 94912, 191562, 380933, 746338, 1444676, 2763931, 5235309, 9822686, 18275648, 33734658, 61826344, 112550305, 203627610, 366267931, 655261559, 1166312530, 2066048261, 3643352362, 6397485909, 11188129665, 19491131627, 33831897511, 58519577756, 100885389220, 173368983090, 297021470421, 507378371670, 864277569606, 1468245046383, 2487774321958, 4204663810414, 7089200255686, 11924621337321, 20012746962064, 33513139512868, 56001473574091, 93387290773141, 155419866337746

Offset: 8

N. J. A. Sloane

nonn

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 8..2500
J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
Index entries for sequences related to trees

Cf. A034853, A000306 (diameter 8)

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:
g:= n-> b((n-1)$2, 3) -b((n-1)$2, 2):
a:= n-> (add(g(i)*g(n-i), i=0..n)+`if`(n::even, g(n/2), 0))/2:
seq(a(n), n=8..40);  # Alois P. Heinz, Feb 09 2016

m = 50; r[x_] = (Rest @ CoefficientList[ Series[ x*Product[ (1 - x^k)^(- PartitionsP[k-1]), {k, 1, m+3}], {x, 0, m+3}], x] - PartitionsP[ Range[0, m+2]]).(x^Range[m+3]); A000550 = CoefficientList[(r[x]^2 + r[x^2])/2, x][[9 ;; m+8]] (* Jean-François Alcover, Feb 09 2016 *)

G.f.: a(x)=(r(x)^2+r(x^2))/2, where r(x) is the generating function of A000235. - Sean A. Irvine, Nov 21 2010

More terms from Sean A. Irvine, Nov 21 2010

A034825 Number of n-node rooted trees of height at most 8.

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 20, 48, 115, 286, 718, 1832, 4702, 12159, 31515, 81888, 212878, 553557, 1438741, 3737331, 9700188, 25156049, 65181067, 168746672, 436505846, 1128256918, 2914103577, 7521450053, 19400577711, 50010551503, 128841990772, 331754004302

Offset: 0

N. J. A. Sloane

nonn

N. J. A. Sloane, Table of n, a(n) for n=0..200
N. J. A. Sloane, Transforms
Index entries for sequences related to rooted trees

See A001383 for details.

For Maple program see link in A000235.
with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d,j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: shr:= proc(p) n->`if`(n=0, 1,p(n-1)) end: b[0]:= etr(n->1): for j from 1 to 6 do b[j]:= etr(shr(b[j-1])) od: a:= shr(b[6]): seq(a(n), n=0..31); # Alois P. Heinz, Sep 08 2008

Prepend[Nest[CoefficientList[Series[Product[1/(1-x^i)^#[[i]], {i, 1, Length[#]}], {x, 0, 40}], x]&, {1}, 8], 1] (* Geoffrey Critzer, Aug 01 2013 *)

Take Euler transform of A034824 and shift right. (Christian G. Bower).

A000299 Number of n-node rooted trees of height 4.

Original entry on oeis.org

0, 0, 0, 0, 1, 4, 13, 36, 93, 225, 528, 1198, 2666, 5815, 12517, 26587, 55933, 116564, 241151, 495417, 1011950, 2055892, 4157514, 8371318, 16792066, 33564256, 66875221, 132849983, 263192599, 520087551, 1025295487, 2016745784, 3958608430, 7754810743

Offset: 1

N. J. A. Sloane

nonn

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..1000 (first 200 terms from N. J. A. Sloane)
F. Harary & R. W. Robinson, The number of achiral trees, Jnl. Reine Angewandte Mathematik 278 (1975), 322-335. (Annotated scanned copy)
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)
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Column h=4 of A034781.

Maple
```
For Maple program see link in A000235.
```

f[n_] := Nest[CoefficientList[Series[Product[1/(1 - x^i)^#[[i]], {i, 1, Length[#]}], {x, 0, 40}], x] &, {1}, n];f[4]-f[3] (* Geoffrey Critzer, Aug 01 2013 *)

Cf. A001384-A001383. - Christian G. Bower

A000342 Number of n-node rooted trees of height 5.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 5, 19, 61, 180, 498, 1323, 3405, 8557, 21103, 51248, 122898, 291579, 685562, 1599209, 3705122, 8532309, 19543867, 44552066, 101124867, 228640542, 515125815, 1156829459, 2590247002, 5784031485, 12883390590, 28629914457

Offset: 1

N. J. A. Sloane

nonn

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n=1..200
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)
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Column h=5 of A034781.

Maple
```
For Maple program see link in A000235.
```

f[n_] := Nest[CoefficientList[Series[Product[1/(1 - x^i)^#[[i]], {i, 1, Length[#]}], {x, 0, 40}], x] &, {1}, n];f[5]-f[4] (* 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}]]]; a[n_] := b[n- 1, n-1, 5] - b[n-1, n-1, 4]; Array[a, 40] (* Jean-François Alcover, Feb 07 2016, after Alois P. Heinz in A034781 *)

A001385-A001384. (Christian G. Bower).

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

A001383 Number of n-node rooted trees of height at most 3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A001385 Number of n-node trees of height at most 5.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A034823 Number of n-node rooted trees of height at most 6.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A001384 Number of n-node trees of height at most 4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A034824 Number of n-node rooted trees of height at most 7.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A000550 Number of trees of diameter 7.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple