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

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,6

Comments

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

Links

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

Example

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

Mathematica

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<Count[#, {}, {-2}]&]], {n, 1, 10}]

Prog

(PARI) \\ 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

Crossrefs

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.

Sequence in context: A048010 A002571 A077916 * A189315 A056422 A032296

Adjacent sequences: A358725 A358726 A358727 * A358729 A358730 A358731

Keyword

nonn

Author

Gus Wiseman, Nov 29 2022

Extensions

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

Status

approved