A034781 -id:A034781 - cp's OEIS frontend

A358725 Matula-Goebel numbers of rooted trees with a greater number of internal (non-leaf) vertices than edge-height.

9, 15, 18, 21, 23, 25, 27, 30, 33, 35, 36, 39, 42, 45, 46, 47, 49, 50, 51, 54, 55, 57, 60, 61, 63, 65, 66, 69, 70, 72, 73, 75, 77, 78, 81, 83, 84, 85, 87, 90, 91, 92, 93, 94, 95, 97, 98, 99, 100, 102, 103, 105, 108, 110, 111, 113, 114, 115, 117, 119, 120, 121

Offset: 1

Gus Wiseman, Nov 29 2022

nonn

Edge-height (A109082) is the number of edges in the longest path from root to leaf.

The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of the branches of its root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.

			The terms together with their corresponding trees begin:
   9: ((o)(o))
  15: ((o)((o)))
  18: (o(o)(o))
  21: ((o)(oo))
  23: (((o)(o)))
  25: (((o))((o)))
  27: ((o)(o)(o))
  30: (o(o)((o)))
  33: ((o)(((o))))
  35: (((o))(oo))
  36: (oo(o)(o))
  39: ((o)(o(o)))
  42: (o(o)(oo))
  45: ((o)(o)((o)))
  46: (o((o)(o)))
  47: (((o)((o))))
  49: ((oo)(oo))
  50: (o((o))((o)))

Gus Wiseman, The first 64 ordered trees with a greater number of internal vertices than edge-height.

Complement of A209638 (the case of equality).
These trees are counted by A316321.
Positions of positive terms in A358724.
The case of equality for node-height is A358576.
A000081 counts rooted trees, ordered A000108.
A034781 counts rooted trees by nodes and height, ordered A080936
A055277 counts rooted trees by nodes and leaves, ordered A001263.
Differences: A358580, A358724, A358726, A358729.
MG statistics: A061775, A109082, A109129, A196050, A342507, A358552.
MG core: A000040, A000720, A001222, A007097, A056239, A112798.
Cf. A185650, A206487, A358577, A358578, A358581-A358586, A358587, A358592, A358730.

MGTree[n_]:=If[n==1,{},MGTree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Count[MGTree[#],[_],{0,Infinity}]>Depth[MGTree[#]]-2&]

A342507(a(n)) > A109082(a(n)).

A358730 Positions of first appearances in A358729 (number of nodes minus node-height).

Original entry on oeis.org

1, 4, 8, 16, 27, 54, 81, 162, 243, 486, 729, 1458, 2187, 4374, 6561, 13122, 19683, 39366, 59049

Offset: 1

Gus Wiseman, Dec 01 2022

First differs from A334198 in having 13122 instead of 12005.
Node-height is the number of nodes in the longest path from root to leaf.
After initial terms, this appears to become A038754.

			The terms together with their corresponding rooted trees begin:
      1: o
      4: (oo)
      8: (ooo)
     16: (oooo)
     27: ((o)(o)(o))
     54: (o(o)(o)(o))
     81: ((o)(o)(o)(o))
    162: (o(o)(o)(o)(o))
    243: ((o)(o)(o)(o)(o))
    486: (o(o)(o)(o)(o)(o))
    729: ((o)(o)(o)(o)(o)(o))

Positions of first appearances in A358729.
A000081 counts rooted trees, ordered A000108.
A034781 counts rooted trees by nodes and height.
A055277 counts rooted trees by nodes and leaves.
MG differences: A358580, A358724, A358726, A358729.
MG statistics: A061775, A109082, A109129, A196050, A342507, A358552.
MG core: A000040, A000720, A001222, A007097, A056239, A112798.
Cf. A080936, A206487, A209638, A316321, A358576, A358577, A358592, A358725, A358731.

MGTree[n_]:=If[n==1,{},MGTree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
rd=Table[Count[MGTree[n],_,{0,Infinity}]-(Depth[MGTree[n]]-1),{n,10000}];
Table[Position[rd,k][[1,1]],{k,Union[rd]}]

A245102 Number of 2n-node rooted trees of height n.

Original entry on oeis.org

0, 1, 2, 8, 36, 180, 941, 5079, 27961, 156129, 880883, 5009625, 28668920, 164897622, 952418882, 5520254925, 32090787577, 187030223470, 1092467751427, 6393706661582, 37484034980109, 220093799592140, 1294100839792723, 7618482099893824, 44901233075819275

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

a(n) ~ c * d^n / sqrt(n), where d = 6.0313827950978605329935..., c = 0.03944957121899527... . - Vaclav Kotesovec, Jul 12 2014

A291336 Number F(n,h,t) of forests of t unlabeled rooted trees with n vertices such that h is the maximum of 0 and the tree heights; triangle of triangles F(n,h,t), n>=0, h=0..n, t=0..n-h, read by layers, then by rows.

Original entry on oeis.org

1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 2, 1, 0, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 2, 1, 0, 4, 3, 1, 0, 3, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 3, 3, 2, 1, 0, 6, 8, 3, 1, 0, 8, 4, 1, 0, 4, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 3, 4, 3, 2, 1, 0, 10, 15, 9, 3, 1, 0, 18, 13, 4, 1, 0, 13, 5, 1, 0, 5, 1, 0, 1, 0

Offset: 0

Alois P. Heinz, Aug 22 2017

Elements in rows h=0 give A023531.
Positive elements in rows h=1 give A008284.
Positive row sums per layer (and - with a different offset - positive elements in column t=1) give A034781.
Positive column sums per layer give A033185.

			n h\t: 0 1 2 3 4 5 : A034781 : A033185   : A000081
-----+-------------+---------+-----------+--------
0 0  : 1           :         :           : 1
-----+-------------+---------+-----------+--------
1 0  : 0 1         :       1 : .         :
1 1  : 0           :         : 1         : 1
-----+-------------+---------+-----------+--------
2 0  : 0 0 1       :       1 : . .       :
2 1  : 0 1         :       1 : .         :
2 2  : 0           :         : 1 1       : 2
-----+-------------+---------+-----------+--------
3 0  : 0 0 0 1     :       1 : . . .     :
3 1  : 0 1 1       :       2 : . .       :
3 2  : 0 1         :       1 : .         :
3 3  : 0           :         : 2 1 1     : 4
-----+-------------+---------+-----------+--------
4 0  : 0 0 0 0 1   :       1 : . . . .   :
4 1  : 0 1 2 1     :       4 : . . .     :
4 2  : 0 2 1       :       3 : . .       :
4 3  : 0 1         :       1 : .         :
4 4  : 0           :         : 4 3 1 1   : 9
-----+-------------+---------+-----------+--------
5 0  : 0 0 0 0 0 1 :       1 : . . . . . :
5 1  : 0 1 2 2 1   :       6 : . . . .   :
5 2  : 0 4 3 1     :       8 : . . .     :
5 3  : 0 3 1       :       4 : . .       :
5 4  : 0 1         :       1 : .         :
5 5  : 0           :         : 9 6 3 1 1 : 20
-----+-------------+---------+-----------+--------

Alois P. Heinz, Layers n = 0..48, flattened

Cf. A000007, A000041, A000065, A000081, A001853, A005197, A008284, A023531, A033185, A034781, A291203, A291204, A291529.

b:= proc(n, i, t, h) option remember; expand(`if`(n=0 or h=0
       or i=1, x^(t*n), b(n, i-1, t, h)+add(x^(t*j)*binomial(
       b(i-1$2, 0, h-1)+j-1, j)*b(n-i*j, i-1, t, h), j=1..n/i)))
    end:
g:= (n, h)-> b(n$2, 1, h)-`if`(h=0, 0, b(n$2, 1, h-1)):
F:= (n, h, t)-> coeff(g(n, h), x, t):
seq(seq(seq(F(n, h, t), t=0..n-h), h=0..n), n=0..9);

b[n_, i_, t_, h_] := b[n, i, t, h] = Expand[If[n == 0 || h == 0
     || i == 1, x^(t*n), b[n, i-1, t, h] + Sum[x^(t*j)*Binomial[
     b[i-1, i-1, 0, h-1]+j-1, j]*b[n - i*j, i-1, t, h], {j, 1, n/i}]]];
g[n_, h_] := b[n, n, 1, h] - If[h == 0, 0, b[n, n, 1, h-1]];
F[n_, h_, t_] := Coefficient[g[n, h], x, t];
Table[Table[Table[F[n, h, t], {t, 0, n-h}], {h, 0, n}], {n, 0, 9}] //
Flatten (* Jean-François Alcover, Mar 10 2022, after Alois P. Heinz *)

Sum_{d=0..n} Sum_{i=0..d} F(n,i,d-i) = A000081(n+1).
Sum_{h=0..n} Sum_{t=0..n-h} t * F(n,h,t) = A005197(n).
Sum_{h=0..n} Sum_{t=0..n-h} (h+1) * F(n,h,t) = A001853(n+1) for n>0.
Sum_{t=0..n-1} F(n,1,t) = A000065(n) = A000041(n) - 1.
F(n,1,1) = 1 for n>1.
F(n,0,0) = A000007(n).

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

A358728 Number of n-node rooted trees whose node-height is less than their number of leaves.

Original entry on oeis.org

0, 0, 0, 1, 1, 5, 10, 30, 76, 219, 582, 1662, 4614, 13080, 36903, 105098, 298689, 852734, 2434660, 6964349, 19931147, 57100177, 163647811, 469290004, 1346225668, 3863239150, 11089085961, 31838349956, 91430943515, 262615909503, 754439588007, 2167711283560

Offset: 1

Gus Wiseman, Nov 29 2022

nonn

Node-height is the number of nodes in the longest path from root to leaf.

			The a(1) = 0 through a(7) = 10 trees:
  .  .  .  (ooo)  (oooo)  (ooooo)   (oooooo)
                          ((oooo))  ((ooooo))
                          (o(ooo))  (o(oooo))
                          (oo(oo))  (oo(ooo))
                          (ooo(o))  (ooo(oo))
                                    (oooo(o))
                                    ((o)(ooo))
                                    ((oo)(oo))
                                    (o(o)(oo))
                                    (oo(o)(o))

Andrew Howroyd, Table of n, a(n) for n = 1..200

These trees are ranked by A358727.
For internals instead of node-height we have A358581, ordered A358585.
The case of equality is A358589 (square trees), ranked by A358577.
A000081 counts rooted trees, ordered A000108.
A034781 counts rooted trees by nodes and height, ordered A080936.
A055277 counts rooted trees by nodes and leaves, ordered A001263.
Cf. A109082, A109129, A185650, A358552, A358582-A358586, A358587, A358591.

art[n_]:=If[n==1,{{}},Join@@Table[Select[Tuples[art/@c],OrderedQ],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[art[n],Depth[#]-1

\\ Needs R(n,f) defined in A358589.
seq(n) = {Vec(R(n, (h,p)->sum(j=h+1, n-1, polcoef(p,j,y))), -n)} \\ Andrew Howroyd, Jan 01 2023

Terms a(19) and beyond from Andrew Howroyd, Jan 01 2023

A358731 Matula-Goebel numbers of rooted trees whose number of nodes is one more than their node-height.

Original entry on oeis.org

4, 6, 7, 10, 13, 17, 22, 29, 41, 59, 62, 79, 109, 179, 254, 277, 293, 401, 599, 1063, 1418, 1609, 1787, 1913, 2749, 4397, 8527, 10762, 11827, 13613, 15299, 16519, 24859, 42043, 87803

Offset: 1

Gus Wiseman, Dec 01 2022

These are paths with a single extra leaf growing from them.
The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of the branches of its root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.
Node-height is the number of nodes in the longest path from root to leaf.

			The terms together with their corresponding rooted trees begin:
    4: (oo)
    6: (o(o))
    7: ((oo))
   10: (o((o)))
   13: ((o(o)))
   17: (((oo)))
   22: (o(((o))))
   29: ((o((o))))
   41: (((o(o))))
   59: ((((oo))))
   62: (o((((o)))))
   79: ((o(((o)))))
  109: (((o((o)))))
  179: ((((o(o)))))
  254: (o(((((o))))))
  277: (((((oo)))))
  293: ((o((((o))))))
  401: (((o(((o))))))
  599: ((((o((o))))))

These trees are counted by A289207.
Positions of 1's in A358729.
A000081 counts rooted trees, ordered A000108.
A034781 counts rooted trees by nodes and height.
A055277 counts rooted trees by nodes and leaves.
MG differences: A358580, A358724, A358726, A358729.
MG statistics: A061775, A109082, A109129, A196050, A342507, A358552.
MG core: A000040, A000720, A001222, A007097, A056239, A112798.
Cf. A206487, A209638, A316321, A358576, A358577, A358592, A358725.

MGTree[n_]:=If[n==1,{},MGTree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[1000],Count[MGTree[#],_,{0,Infinity}]==Depth[MGTree[#]]&]

A375467 Triangle read by rows: Number of unlabeled rooted trees with n vertices where the level of a vertex is bounded by k.

Original entry on oeis.org

0, 0, 1, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 3, 4, 0, 0, 1, 5, 8, 9, 0, 0, 1, 7, 15, 19, 20, 0, 0, 1, 11, 29, 42, 47, 48, 0, 0, 1, 15, 53, 89, 108, 114, 115, 0, 0, 1, 22, 98, 191, 252, 278, 285, 286, 0, 0, 1, 30, 177, 402, 582, 676, 710, 718, 719

Offset: 0

Peter Luschny, Aug 29 2024

The level of a vertex is the number of vertices in the path from the root to the vertex, the level of the root is 1.

			Triangle starts:
  [0] [0]
  [1] [0, 1]
  [2] [0, 0, 1]
  [3] [0, 0, 1,  2]
  [4] [0, 0, 1,  3,  4]
  [5] [0, 0, 1,  5,  8,   9]
  [6] [0, 0, 1,  7, 15,  19,  20]
  [7] [0, 0, 1, 11, 29,  42,  47,  48]
  [8] [0, 0, 1, 15, 53,  89, 108, 114, 115]
  [9] [0, 0, 1, 22, 98, 191, 252, 278, 285, 286]

Cf. A000081 (main diagonal), A375468 (row sums), A034781.

div := n -> numtheory:-divisors(n):
H := proc(n, k) option remember; local d; add(d * T(d, k), d = div(n)) end:
T := proc(n, k) option remember; local i; if n = 1 then ifelse(k > 0, 1, 0) else add(T(i, k) * H(n - i, k - 1), i = 1..n - 1) / (n - 1) fi end:
seq(print(seq(T(n, k), k = 0..n)), n = 0..9):  # Peter Luschny, Sep 11 2024

from functools import cache
@cache
def Divisors(n: int) -> list[int]:
    return [d for d in range(n, 0, -1) if n % d == 0]
@cache
def H(n: int, k: int) -> int:
    return sum(d * T(d, k) for d in Divisors(n))
@cache
def T(n: int, k: int) -> int:
    if k == 0: return 0
    if n == 1: return int(k > 0)
    return sum(T(i, k) * H(n - i, k - 1)
           for i in range(1, n) ) // (n - 1)
for n in range(10): print([T(n, k) for k in range(n + 1)])
# Peter Luschny, Sep 11 2024

The rows accumulate the rows of A034781.

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

A358725 Matula-Goebel numbers of rooted trees with a greater number of internal (non-leaf) vertices than edge-height.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A358730 Positions of first appearances in A358729 (number of nodes minus node-height).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A245102 Number of 2n-node rooted trees of height n.

Views

Author

Keywords

Links

Crossrefs

Formula

A291336 Number F(n,h,t) of forests of t unlabeled rooted trees with n vertices such that h is the maximum of 0 and the tree heights; triangle of triangles F(n,h,t), n>=0, h=0..n, t=0..n-h, read by layers, then by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula

A358728 Number of n-node rooted trees whose node-height is less than their number of leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A358731 Matula-Goebel numbers of rooted trees whose number of nodes is one more than their node-height.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A375467 Triangle read by rows: Number of unlabeled rooted trees with n vertices where the level of a vertex is bounded by k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Python

Formula

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